给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

示例 1:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"输出: true

示例 2:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"输出: false

1 //使用动态规划 2 //  Ø d b b c a 3 //Ø T F F F F F 4 //a T F F F F F 5 //a T T T T T F 6 //b F T T F T F 7 //c F F T T T T 8 //c F F F T F T 9 10 class Solution {11 public:12     bool isInterleave(string s1, string s2, string s3) {13         if (s1.size() + s2.size() != s3.size()) return false;14         int n1 = s1.size(), n2 = s2.size();15         vector
     
      
       > dp(n1 + 1, vector
       
        (n2 + 1, false));16         for (int i = 0; i <= n1; ++i) {17             for (int j = 0; j <= n2; ++j) {18                 if (i == 0 && j == 0) {19                     dp[i][j] = true;20                 }21                 else if (i == 0) {22                     dp[i][j] = dp[i][j - 1] && s2[j - 1] == s3[i + j - 1];23                 }24                 else if (j == 0) {25                     dp[i][j] = dp[i - 1][j] && s1[i - 1] == s3[i + j - 1];26                 }27                 else {28                     dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) || (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]);29                 }30             }31         }32         return dp[n1][n2];33     }34 };35 36 //使用带优化的DFS来做37 class Solution {38 public:39     bool isInterleave(string s1, string s2, string s3) {40         if (s1.size() + s2.size() != s3.size()) return false;41         unordered_set
        
          s;42         return helper(s1, 0, s2, 0, s3, 0, s);43     }44     bool helper(string& s1, int i, string& s2, int j, string& s3, int k, unordered_set
         
          & s) {45         int key = i * s3.size() + j;46         if (s.count(key)) return false;47         if (i == s1.size()) return s2.substr(j) == s3.substr(k);48         if (j == s2.size()) return s1.substr(i) == s3.substr(k);49         if ((s1[i] == s3[k] && helper(s1, i + 1, s2, j, s3, k + 1, s)) ||50             (s2[j] == s3[k] && helper(s1, i, s2, j + 1, s3, k + 1, s))) return true;51         s.insert(key);52         return false;53     }54 };55 56 //使用BFS57 class Solution {58 public:59     bool isInterleave(string s1, string s2, string s3) {60         if (s1.size() + s2.size() != s3.size()) return false;61         int n1 = s1.size(), n2 = s2.size(), n3 = s3.size(), k = 0;62         unordered_set
          
            s;63 queue
           
             q{ { 0} };64 while (!q.empty() && k < n3) {65 int len = q.size();66 for (int t = 0; t < len; ++t) {67 int i = q.front() / n3, j = q.front() % n3; q.pop();68 if (i < n1 && s1[i] == s3[k]) {69 int key = (i + 1) * n3 + j;70 if (!s.count(key)) {71 s.insert(key);72 q.push(key);73 }74 }75 if (j < n2 && s2[j] == s3[k]) {76 int key = i * n3 + j + 1;77 if (!s.count(key)) {78 s.insert(key);79 q.push(key);80 }81 }82 }83 ++k;84 }85 return !q.empty() && k == n3;86 }87 };