-
Notifications
You must be signed in to change notification settings - Fork 0
/
_0097_main.cpp
38 lines (31 loc) · 1.04 KB
/
_0097_main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// Created by WXX on 2021/1/25 16:29
#include <iostream>
#include <vector>
using namespace std;
/**
* 执行用时:8 ms, 在所有 C++ 提交中击败了46.88%的用户
* 内存消耗:6.5 MB, 在所有 C++ 提交中击败了82.73%的用户
*/
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int n = s1.size(), m = s2.size();
if (s3.size() != n + m) return false;
vector<vector<bool>> f(n + 1, vector<bool>(m + 1));
s1 = ' ' + s1, s2 = ' ' + s2, s3 = ' ' + s3;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m; j++) {
if (!i && !j) f[i][j] = true;
else {
if (i && s1[i] == s3[i + j]) f[i][j] = f[i - 1][j];
if (j && s2[j] == s3[i + j]) f[i][j] = f[i][j] || f[i][j - 1];
}
}
return f[n][m];
}
};
int main() {
string s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac";
cout << Solution().isInterleave(s1, s2, s3) << endl; // true
return 0;
}