[LeetCode]97. Interleaving String

正午 2020-01-10 PM 17℃ 0条

问题描述

原题链接

解法一 动态规划

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int lens1 = s1.length();
        int lens2 = s2.length();
        int lens3 = s3.length();
        if  ( (lens1 + lens2) != lens3){
            return false;
        }
        vector<vector<bool>> dp(lens1+1, vector<bool>(lens2+1));
        dp[0][0] = true;
        for(int i=1; i<=lens1; i++){
            dp[i][0]=s3[i-1]==s1[i-1] && dp[i-1][0];
        }
        for(int j=1; j<=lens2; j++){
            dp[0][j] = s3[j-1] == s2[j-1] && dp[0][j-1];
        }
        for(int i=1; i<=lens1; i++){
            for(int j=1; j<=lens2; j++){
                dp[i][j]=( s3[i+j-1]==s1[i-1] && dp[i-1][j]) || (s3[i+j-1]==s2[j-1]  && dp[i][j-1]); 
            }
        }
        return dp[lens1][lens2];
    }
};
标签: none

非特殊说明,本博所有文章均为博主原创。

评论