dfs: 題意就是s1和s2是否可以交叉變成s3，一開始我使用dfs，但是超時了 然后剪枝，加入一個標記數組，如果dfs過的就不進行dfs，然后就ac了
class Solution {public: int mapp[500][500]; int mark = 0; void pipei(string s1, string s2, string s3, int a, int b, int c){ if(mark) return ; mapp[a][b] = 1; if(a + 1 == s1.length() && b == s2.length() && c + 1 == s3.length() && s1[a] == s3[c]){ mark = 1; return ; } else if(a == s1.length() && b + 1 == s2.length() && c + 1 == s3.length() && s2[b] == s3[c]){ mark = 1; return ; } else if(a < s1.length() && b < s2.length()){ if(s1[a] == s3[c] && !mapp[a + 1][b]) pipei(s1, s2, s3, a + 1, b, c + 1); if(s2[b] == s3[c] && !mapp[a][b + 1]) pipei(s1, s2, s3, a, b + 1, c + 1); } else if(a < s1.length()){ if(s1[a] == s3[c] && !mapp[a + 1][b]) pipei(s1, s2, s3, a + 1, b, c + 1); } else if(b < s2.length()){ if(s2[b] == s3[c] && !mapp[a][b + 1]) pipei(s1, s2, s3, a, b + 1, c + 1); } return ; } bool isInterleave(string s1, string s2, string s3) { if(s1.length() + s2.length() != s3.length()) return false; if(s1.length() == 0 && s2.length() == 0 && s3.length() == 0) return true; memset(mapp, 0, sizeof(mapp)); pipei(s1, s2, s3, 0, 0, 0); if(mark) return true; else return false; }};dp: 其實這題應該用dp，mapp (i,j)代表到s1 i 和s2 j都可以匹配，然后方程是 if(mapp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) mapp[i][j] = true; if(mapp[i][j - 1] && s2[j - 1] == s3[i + j - 1]) mapp[i][j] = true; 十分好理解
class Solution {public: bool isInterleave(string s1, string s2, string s3) { if(s1.length() + s2.length() != s3.length()) return false; if(s1.length() == 0 && s2.length() == 0 && s3.length() == 0) return true; bool mapp[s1.length() + 1][s2.length() + 1]; memset(mapp, false, sizeof(mapp)); for(int i = 0; i <= s1.length(); ++ i) for(int j = 0; j <= s2.length(); ++ j){ if(i == 0 && j == 0) mapp[i][j] = true; else if(i == 0){ if(mapp[0][j - 1] && s2[j - 1] == s3[j - 1]) mapp[0][j] = true; } else if(j == 0){ if(mapp[i - 1][0] && s1[i - 1] == s3[i - 1]) mapp[i][0] = true; } else{ if(mapp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) mapp[i][j] = true; if(mapp[i][j - 1] && s2[j - 1] == s3[i + j - 1]) mapp[i][j] = true; } } return mapp[s1.length()][s2.length()]; }};新聞熱點
疑難解答
