Interleaving string

String Dynamic Programming

43.6% acceptance

Jan 12, 2026

8809

552

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2. An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such that: s = s1 + s2 + ... + sn t = t1 + t2 + ... + tm |n - m| <= 1 The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ... Note: a + b is the concatenation of strings a and b.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn is_interleave(s1: String, s2: String, s3: String) -> bool {
    let m = s1.len();
    let n = s2.len();
    
    if m + n != s3.len() {
      return false;
    }
    
    let s1 = s1.as_bytes();
    let s2 = s2.as_bytes();
    let s3 = s3.as_bytes();
    
    let mut dp = vec![false; n + 1];
    dp[0] = true;
    
    for j in 1..=n {
      dp[j] = dp[j-1] && s2[j-1] == s3[j-1];
    }
    
    for i in 1..=m {
      dp[0] = dp[0] && s1[i-1] == s3[i-1];
      for j in 1..=n {
        let k = i + j - 1;
        dp[j] = (dp[j] && s1[i-1] == s3[k]) || 
            (dp[j-1] && s2[j-1] == s3[k]);
      }
    }
    
    dp[n]
  }
}