lintcode 交叉字符串

作者: yzawyx0220 | 来源:发表于2016-12-18 18:56 被阅读413次

给出三个字符串:s1、s2、s3,判断s3是否由s1和s2交叉构成。
样例
比如 s1 = "aabcc" s2 = "dbbca"
当 s3 = "aadbbcbcac",返回 true.
当 s3 = "aadbbbaccc", 返回 false.

很多人看到这个题的第一反应是用指针,依次遍历三个字符串,但是那样无法解决选择的问题,比如s1和s2都有相同的一个字母可以和s3匹配,但是由于顺序问题可能就会导致得出错误的结果。

这种类似的字符串问题可以使用动态规划的方法,建立一个二维数组dp,dp[i][j]表示s3可以由s1的前i个和s2的前j个组成,那么子问题就是dp[i-1][j]或者dp[i][j-1],只有子问题成立(true),该问题才会成立。而dp[i-1][j]的子问题是dp[i-2][j]或者dp[i-1][j-1],以此类推,最后都会归结为判断dp[1][0]或者dp[0][1]。

class Solution {
public:
    /**
     * Determine whether s3 is formed by interleaving of s1 and s2.
     * @param s1, s2, s3: As description.
     * @return: true of false.
     */
    bool isInterleave(string s1, string s2, string s3) {
        // write your code here
        if(s3.size() != s1.size() + s2.size())  
            return false;  
        vector<vector<bool> > dp(s1.size() + 1,vector<bool>(s2.size() + 1,false));
        dp[0][0] = true;  
        for(int i = 1;i <= s1.size();i++)  
            dp[i][0] = (dp[i - 1][0] && (s3[i - 1] == s1[i - 1]));  
        for(int i = 1;i <= s2.size();i++)  
            dp[0][i] = (dp[0][i - 1] && (s3[i - 1] == s2[i - 1]));  
        for(int i = 1;i <= s1.size();i++)  
        {  
            for(int j = 1;j <= s2.size();j++)  
            {  
                int t = i + j;  
                if(s1[i - 1] == s3[t - 1])  
                    dp[i][j] = dp[i][j] || dp[i - 1][j];  
                if(s2[j - 1] == s3[t - 1])  
                    dp[i][j] = dp[i][j]||dp[i][j - 1];  
            }  
        }  
        return dp[s1.size()][s2.size()]; 
    }
};

相关文章

  • LintCode交叉字符串

    给出三个字符串:s1、s2、s3,判断s3是否由s1和s2交叉构成。 样例比如 s1 = "aabcc" s2 =...

  • lintcode 交叉字符串

    给出三个字符串:s1、s2、s3,判断s3是否由s1和s2交叉构成。样例比如 s1 = "aabcc" s2 = ...

  • LintCode-交叉字符串-动态规划

    描述 给出三个字符串:s1、s2、s3,判断s3是否由s1和s2交叉构成。 样例 比如 s1 = "aabcc" ...

  • [leetcode/lintcode 题解] 解码字符串 ·

    leetcode/lintcode 题解] 解码字符串 · Decode String 【题目描述】 给出一个表...

  • python 字符串倒置(lintcode)

    描述: 字符串置换 原题地址:http://www.lintcode.com/zh-cn/problem/stri...

  • lintCode题解(8)

    标签(空格分隔): lintCode 旋转字符串 给定一个字符串和一个偏移量,根据偏移量旋转字符串(从左向右旋转)...

  • TypeScript 08 - 高级类型

    交叉类型 联合类型 类型保护 可以为 null 的类型 字符串字面量类型 1. 交叉类型 交叉类型是将多个类型合并...

  • Delete Digits

    Delete Digits 今天是一道有关字符串和贪婪算法的题目,来自LintCode,难度为Medium,Acc...

  • lintcode 字符串查找

    对于一个给定的 source 字符串和一个 target 字符串,你应该在 source 字符串中找出 targe...

  • lintcode 旋转字符串

    给定一个字符串和一个偏移量,根据偏移量旋转字符串(从左向右旋转)题目比较简单,只要注意处理一下旋转的个数大于字符串...

网友评论

    本文标题:lintcode 交叉字符串

    本文链接:https://www.haomeiwen.com/subject/ztlzmttx.html