题解 | #交错编号#

#include <vector>
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
        // 跟 “NB122 交织子序列” 大同小异
        int col = s1.size();
        int row = s2.size();
        int len = s3.size();

        if(col+row != len)
            return false;
        // 
        s1 = " " + s1;
        s2 = " " + s2;
        s3 = " " + s3;

        vector<vector<int> > dp(row+1,vector<int>(col+1,false));
        // 判断是不是s1在前
        bool flag = false;
        // 初始化第一行
        for(int j=0; j<=col; ++j)
        {
            if(s1[j]==s3[j])
                dp[0][j] = true;
            else
                break;

            if(j==col && dp[0][j])
                flag = true;
        }

        // 初始化第一列
        for(int i=0; i<=row; ++i)
        {
            if(s2[i]==s3[i])
                dp[i][0] = true;
            else
                break;
        }
        
        
        // 外层循环为行，内层循环为列，为了让s1先遍历完
        for(int i=1; i<=row; ++i)
        {
            for(int j=1; j<=col; ++j)
            {
                dp[i][j] = (s1[j]==s3[i+j]&&dp[i][j-1]) || (s2[i]==s3[i+j]&&dp[i-1][j]);
                // s1已经遍历完了，且s3中有组成s2的全部字符
                if(j==col && i<row && dp[i][j])
                    flag = true;
            }
        }

        return flag && dp[row][col];
    }
};