力扣算法题—097交错字符串

给定三个字符串 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<vector<bool>> dp(n1 + 1, vector<bool>(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<int> 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<int>& 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 //使用BFS
57 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<int> s;
63         queue<int> 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 };