| 12 | class Solution { |
| 13 | public: |
| 14 | bool isInterleave(string s1, string s2, string s3) { |
| 15 | int l1 = s1.size(), l2 = s2.size(), l3 = s3.size(); |
| 16 | if (l1 + l2 != l3) return false; |
| 17 | vector<vector<bool>> dp (l1 + 1, vector<bool> (l2 + 1, false)); |
| 18 | dp[0][0] = true; |
| 19 | for (int j = 1; j <= l2; j ++) |
| 20 | dp[0][j] = dp[0][j-1] and s3[j-1] == s2[j-1]; |
| 21 | for (int i = 1; i <= l1; i ++) |
| 22 | dp[i][0] = dp[i-1][0] and s3[i-1] == s1[i-1]; |
| 23 | // init finish |
| 24 | for (int i = 1; i <= l1; i ++) { |
| 25 | for (int j = 1; j <= l2; j ++) { |
| 26 | dp[i][j] = dp[i-1][j] and s1[i-1] == s3[i + j - 1] or |
| 27 | dp[i][j-1] and s2[j-1] == s3[i + j - 1]; |
| 28 | } |
| 29 | } |
| 30 | return dp[l1][l2]; |
| 31 | } |
| 32 | }; |
| 33 | |
| 34 | int main() { |
nothing calls this directly
no outgoing calls
no test coverage detected