問題描述 Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example, Given: s1 = “aabcc”, s2 = “dbbca”,
When s3 = “aadbbcbcac”, return true. When s3 = “aadbbbaccc”, return false.
解決思路 使用動態規劃，dp[i][j] 表示 s1[i-1] 和 s2[j-1]能否組合成s3[i+j-1]，若可以，則true，否則false。 初始情況：dp[0][0] = true , dp[i][0] = s1[i-1] == s3[i-1] ? dp[i-1][0] : 0 , dp[0][i] = s2[i-1] == s3[i-1] ? dp[0][i-1] : 0 狀態轉移： if (s3[i+j-1] == s1[i-1]) dp[i][j] = dp[i-1][j]; if (s3[i+j-1] == s2[j-1]) dp[i][j] = dp[i][j-1] || dp[i][j];
代碼
class Solution {public: bool isInterleave(string s1, string s2, string s3) { int m = s1.length(); int n = s2.length(); int l = s3.length(); if (m + n != l) return false; else if (m == 0) return s2 == s3; else if (n == 0) return s1 == s3; vector<vector<bool>> dp(m+1,vector<bool>(n+1,false)); dp[0][0] = true; for (int i = 1; i <= m; ++i) dp[i][0] = s1[i-1] == s3[i-1] ? dp[i-1][0] : 0; for (int i = 1; i <= n; ++i) dp[0][i] = s2[i-1] == s3[i-1] ? dp[0][i-1] : 0; for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (s3[i+j-1] == s1[i-1]) dp[i][j] = dp[i-1][j]; if (s3[i+j-1] == s2[j-1]) dp[i][j] = dp[i][j-1] || dp[i][j]; } } return dp[m][n]; }};新聞熱點
疑難解答
