Leetcode Problem 97. Interleaving String

97. Interleaving String

Leetcode Solutions

UsingD Dynamic Programming

  1. Initialize a 2D boolean array dp with dimensions (len(s1)+1) x (len(s2)+1).
  2. Set dp[0][0] to true as an empty string is an interleaving of two empty strings.
  3. Fill the first row and first column of dp based on whether previous characters of s1 or s2 match with s3.
  4. Iterate over the dp table starting from dp[1][1].
  5. For each cell dp[i][j], set it to true if either dp[i-1][j] is true and s1[i-1] matches s3[i+j-1], or dp[i][j-1] is true and s2[j-1] matches s3[i+j-1].
  6. The answer is the value at dp[len(s1)][len(s2)].
UML Thumbnail

UsingD Dynamic Programming

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...