题解 | #交织子序列#

题目考察的知识点：动态规划

本题解析所用的编程语言：c++

动态规划解法：构造一个(m+1)*(n+1)的dp数组，dp[i][j]表示的是s[1,i]及x[1,j]区间的字符串能否拼接凑成t[1,i+j]区间内的字符串；然后根据最后一个位置分情况讨论

    bool isInterleave(string s, string x, string t)
    {
        // write code here
        int m = s.size(), n = x.size();
        if (m + n != t.size())
            return false;
        s = ' ' + s, x = ' ' + x, t = ' ' + t;//也可以不用加' ',只不过将s、x、t字符串与dp数组对应起来；
	  										  //不加' ',只需将s[i]等改为是s[i-1]即可

        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        dp[0][0] = true;
        for (int j = 1; j <= n; ++j) //初始化第一行
            if (x[j] == t[j])
                dp[0][j] = true;
            else
                break;
        for (int i = 1; i <= m; ++i) //初始化第一列
            if (s[i] == t[i])
                dp[i][0] = true;
            else
                break;
                
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                dp[i][j] = (s[i] == t[i + j] && dp[i - 1][j])
                        || (x[j] == t[i + j] && dp[i][j - 1]);
        
        return dp[m][n];
    }

错误解法：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param x string字符串 
     * @param t string字符串 
     * @return bool布尔型
     */
    bool isInterleave(string s, string x, string t)
    {
        // write code here
        int i = 0, j = 0, k = 0;
        for (k = 0; k < t.size(); ++k)
        {
            if (s[i] == t[k])
                ++i;
            else if (x[j] == t[k])
                ++j;
            else  
                break;
        }

        if (i == s.size() && j == x.size() && k == t.size())
            return true;
        else
            return false;
    }
};