leetcode-97 Interleaving String

发表于

题目

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

1
2
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

1
2
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

解法

描述相当简略的一道题。大概意思是字符串s3可由s1与s2间的内容拼接而成，而且可以是s1、s2分成许多段来拼接，只要最后选择的字串段仍旧按照s1、s2本来的字符顺序就可以。

很快能够想到这题可以使用动态规划的方法来做：子问题即每次选择字符进行拼接时选择s1或s2。那么如何来评估这个子问题呢？这里选择维护一个二维vector，假设为f。f[i][j]就代表已选择了s1中i个元素，s2中j个元素的情况下能否拼接成功（拼接成s3中前i+j个元素）。根据前面计算过的值来计算本次的f[i][j]。若两字符串s1、s2的长度分别为m、n，s3的长度为k，那么最后只需判断f[m][n]是否为1就行了（若m+n不等于k则一定无法拼接成功）。

实际实现如下：

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
bool isInterleave(string s1, string s2, string s3) {
    vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, 0));
    int dir[2][2] = {{-1, 0}, {0, -1}};
    if(s1.size() + s2.size() == s3.size()){
        dp[0][0] = 1;
    }
    for(int i = 0; i < dp.size(); ++i){
        for(int j = 0; j < dp[0].size(); ++j){
            if(i == 0 && j == 0) continue;
            for(int m = 0; m < 2; ++m){
                int x = i + dir[m][0], y = j + dir[m][1];
                if(x < 0 || y < 0) continue;
                if(dp[x][y] == 1){
                    if(x < i && s1[i-1] == s3[i+j-1]){
                        dp[i][j] = 1;
                    }
                    if(y < j && s2[j-1] == s3[i+j-1]){
                        dp[i][j] = 1;
                    }
                }
            }
        }
    }
    return dp[s1.size()][s2.size()];
}