[leetcode_97]Interleaving String

Given strings s1 and s2, determine whether s3 is formed by interleaving s1 and s2 while preserving their original order.
Initially I tried simulation, but there is a problem: what if s1[p1] and s2[p2] are both equal to s3[p3]? In that case, we would need to save state and perform a search.
As expected, it timed out.
I found online that DP can be used:
f[i][j] = f[i-1][j] + s1[i] && s1[i] == s3[k]
f[i][j] = f[i][j-1](i+j = k) && s2[j] == s3[j]
The k-th character in s3 is fully matched only when it equals either the i-th character of s1 or the j-th character of s2.
Enumerate all cases, at most n^2.
Output f[i][j] where i = s1.length(), j = s2.length(), and i+j = s3.length().

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    bool ***f;
    bool isInterleave(string s1, string s2, string s3) {
        if(s1.length() + s2.length() != s3.length())return false;
        bool f[500][500];
        for(int i = 0;i < 500;i++) {
            for(int j = 0;j < 500;j++) {
                f[i][j] = false;
            }
        }
        f[0][0] = true;
        for(int i = 1;i <= s3.length();i++) {
            for(int j = 0;j < i;j++) {
                if(f[j][i-1-j] && i-1-j<=s2.length() && j+1 <= s1.length() && s1[j] == s3[i-1]) {
                    f[j+1][i-1-j] = true;
                }
                if(f[j][i-1-j] && j <= s1.length() && i-1-j+1 <= s2.length() && s2[i-1-j] == s3[i-1]) {
                    f[j][i-1-j+1] = true;
                }
            }
        }
        return f[s1.length()][s2.length()];
    }
};