[Leetcode Solution] Interleaving String

GOOD PROBLEM

Analysis

• DP problem
• Let bool f[i][j] denote if sub string of s1 with length i and sub string of s2 with length j and interleave the sub string of s3 with length i+j
• Then f[i][j]==true iff
• s1[i]==s3[i+j] && f[i-1][j] or
• s2[j]==s3[i+j] && f[i][j]

Note

Code