【Leetcode】97. Interleaving String（动态规划）（字符串组合）

た入场券 2022-02-20 13:41 189阅读 0赞

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

**Example 1:**

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

**Example 2:**

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

题目大意：

s3是否可以通过s1和s2交叉得出。

解题思路：

开始通过搜索发现直接超时，所以此题应该通过动态规划求解。

动态规划应该维护一个二维数组，其中（0,0）应该为true，且在第一行第一列的初始化应该根据（0,0）和前一行和前一列是否为true。

在中间部分的维护需要根据前一列和前一行是否为True，若为True即为前一部分即为满足条件，则将本位置标记位True。

class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            
            if(s3.length() != s1.length()+s2.length()) return false;
            
            int l1 = s1.length(), l2 = s2.length(), l3 = s3.length();
            
            bool map[l1+1][l2+1];
            
            for(int i = 0;i<=l1;i++){
                for(int j = 0;j<=l2;j++){
                    
                    if(i==0&&j==0){
                        map[i][j] =true;
                    }
                    
                    else if(i==0){
                        map[i][j] = (map[i][j-1] && s2[j-1] == s3[i+j-1]);
                    }
                    else if(j==0){
                        map[i][j] = (map[i-1][j] && s1[i-1] == s3[i+j-1]);
                    }
                    else{
                        map[i][j] = (map[i][j-1] && s2[j-1] == s3[i+j-1]) || (map[i-1][j] && s1[i-1] == s3[i+j-1]);
                    }
                    
                }
            }
            return map[l1][l2];
        }
    };