首页 > 代码库 > LeetCode: Interleaving String [097]

LeetCode: Interleaving String [097]

2024-07-06 21:29:11   227人阅读

【题目】

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

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.



【题意】

    给定字符串s1,s2,s3, 判断s3是不是s1和s2中的字交叉组合而成。注意，s1,s2中的字符相对位置在s3中不发生改变


【思路】

    典型的DP问题.
    我们假设A[i][j]表示s1[1...i]和s2[1...j]能否交叉构成s3[1...i+j]
    
    A[i-1][j-1]  A[i-1][j]
    A[i][j-1]    A[i][j]
    
    如果A[i-1][j]=true, 表示s1[1...i-1]和s2[1...j]能交叉构成s3[1...i+j-1]。则要看s1[1...i-1, i]和s2[1...j]能交叉构成s3[1...i+j]是只要看s1[i]是否与s3[i+j]相等。
    如果A[i][j-1]=true, 表示s1[1...i]和s2[1...j-1]能交叉构成s3[1...i+j-1]。则要看s1[1...i]和s2[1...j-1, j]能交叉构成s3[1...i+j]是只要看s2[j]是否与s3[i+j]相等。
    
    可见A[i][j]可以由A[i-1][j]和A[i][j-1]两个方向来推断，我们只需要有一个方向为true即可。因此迭代方程如下所示：
    A[i][j]=(A[i-1][j]&&s1[i]==s3[i+j])||(A[1][j-1]&&s2[j]==s3[i+j])


【代码】

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if(s1.length()+s2.length()!=s3.length())return false;
        
        vector<vector<bool> >matrix(s1.length()+1, vector<bool>(s2.length()+1, false));
        //初始化matrix[0][0];
        matrix[0][0]=true;
        //初始化第一行
        for(int j=1; j<=s2.length(); j++){
            matrix[0][j]= matrix[0][j-1]&&s2[j-1]==s3[j-1];
        }
        //初始化第一列
        for(int i=1; i<=s1.length(); i++){
            matrix[i][0]= matrix[i-1][0]&&s1[i-1]==s3[i-1];
        }
        //初始化其他单元
        for(int i=1; i<=s1.length(); i++){
            for(int j=1; j<=s2.length(); j++){
                matrix[i][j]=(matrix[i-1][j]&&s1[i-1]==s3[i+j-1])||(matrix[i][j-1]&&s2[j-1]==s3[i+j-1]);
            }
        }
        return matrix[s1.length()][s2.length()];
    }
};


联系
我们