【NowCoder LeetCode】interleaving-string 动态规划

痛定思痛。 2022-11-25 13:19 124阅读 0赞

#### 题目链接：[interleaving-string][] ####

#### 题意： ####

判断s3是否可以在不改变s1、s2字符顺序的情况下，由s1和s2交织而成。

#### 思路： ####

一开始我的想法是模拟字符串s3的每一个字符，判断s3的当前字符是否为s1、s2当前字符其中的一个，但后来发现会出现问题，因为如果s1和s2当前所在的字符和s3当前的字符都相等的话，这时候就要分两种情况判断，但是后面的字符同样也会出现这种情况，就导致可能会分为4、8、16…多的情况，因此是行不通的。

那么如何使用动态规划解决呢？

首先根据题意，如果长度为 len1 的 s1 和长度为 len2 的 s2 能交织成长度为 len3 的 s3，那么长度为 len1-1 的 s1\[0 , len1-1\] 和 长度为 len2 的 s2 就能交织成长度为 len3-1 的 s3\[0 , len3-1\] 或 长度为 len1 的 s1 和 长度为 len2-1 的 s2\[0 , len2-1\] 能交织成长度为 len3-1 的 s3\[0 , len3-1\] ；…

以此类推 … 若长度为 i 的 s1\[0 , i \] 和长度为 j 的 s2\[0 , j\] 能交织成长度为 i+j 的 s3\[0 , i+j\] ，那么长度为 i-1 的 s1\[0 , i-1 \] 和 长度为 j 的 s2\[0 , j\] 就能交织成长度为 i+j-1 的 s3\[0 , i+j-1\] 或 长度为 i 的 s1\[0 , i \] 和 长度为 j-1 的 s2\[0 , j-1\] 能交织成长度为 i+j-1 的 s3\[0 , i+j-1\] 。

（由于s3的第 i+j-1 个字符要么来自 s1\[ i-1 \] ，要么来自 s2\[ j-1 \] ）那么，反过来再看，如果长度为 i-1 的 s1 和 长度为 j 的 s2 能交织成长度为 i+j-1 的 s3，那么只要满足 s1\[ i-1 \] = s3\[ i+j-1 \] ，则长度为 i 的 s1 和 长度为 j 的 s2 就能交织成长度为 i+j 的 s3；或者长度为 i 的 s1 和 长度为 j-1 的 s2 能交织成长度为 i+j-1 的 s3 ，且 s2\[ j-1 \] = s3\[ i+j-1 \]，长度为 i 的 s1 和 长度为 j 的 s2 也能交织成长度为 i+j 的 s3。

因此，慢慢思考，假定dp\[ i \]\[ j \]指的是长度为 i 的 s1 和长度为 j 的 s2 能否交织成长度为 i+j 的 s3 ，则推出动态方程为dp\[ i \]\[ j \] = （dp\[ i-1 \]\[ j \] && s1\[ i-1 \] == s3\[ i+j-1 \] ）||（dp\[ i \]\[ j-1 \] && s2\[ j-1 \] == s3\[ i+j-1 \] ）

然后可以使用样例验证一下：  
![样例一][resize_p_60]

#### 代码 ####

class Solution {
        
    public:
        /**
         * 
         * @param s1 string字符串 
         * @param s2 string字符串 
         * @param s3 string字符串 
         * @return bool布尔型
         */
        bool isInterleave(string s1, string s2, string s3) {
        
            // write code here
            int len1 = s1.length();
            int len2 = s2.length();
            int len3 = s3.length();
            if(len3 != len1+len2) return false;
            vector<vector<bool>> dp(len2+1, vector<bool>(len1+1));
            dp[0][0] = true;
            for(int i = 1; i < len1+1; i++){
        
                if(dp[0][i-1] == false) dp[0][i] = false;
                else{
        
                    if(s1[i-1] == s3[i-1]) dp[0][i] = true;
                    else dp[0][i] = false;
                }
            }
            for(int i = 1; i < len2+1; i++){
        
                if(dp[i-1][0] == false) dp[i][0] = false;
                else{
        
                    if(s2[i-1] == s3[i-1]) dp[i][0] = true;
                    else dp[i][0] = false;
                }
            }
            for(int i = 1; i < len2+1; i++){
        
                for(int j = 1; j < len1+1; j++){
        
                    if(dp[i-1][j] == false && dp[i][j-1] == false) 
                        dp[i][j] = false;
                    else if(dp[i-1][j] == true && s3[i+j-1] == s2[i-1])
                        dp[i][j] = true;
                    else if(dp[i][j-1] == true && s3[i+j-1] == s1[j-1])
                        dp[i][j] = true;
                    else dp[i][j] = false;
                }
            }
            return dp[len2][len1];
        }
    };

[interleaving-string]: https://www.nowcoder.com/practice/4d0f94617e454e2da23e660cded4d9e8?tpId=46&&tqId=29081&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
[resize_p_60]: /images/20221124/5afc5be7939742beb076f37f5929a01a.png