Interleaving String
Interleaving String
Finley.Hamilton 发表于3年前
Interleaving String
  • 发表于 3年前
  • 阅读 556
  • 收藏 1
  • 点赞 0
  • 评论 0

腾讯云 十分钟定制你的第一个小程序>>>   

摘要: 动态规划,好久没做了,这道题目好像半年前在TopCoder的时候就一直没想出来

题目

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

For example, Given: s1 = "aabcc", s2 = "dbbca",

When s3 = "aadbbcbcac", return true. When s3 = "aadbbbaccc", return false.

分析

  • 最直观的当然是递归了
  • 因为是两个变量,二维矩阵是少不了的
  • d[i][j]可以表达,当s1取前i个,s2取前j个,是否可以组成s3取前i+j个?
  • 编程上面有技巧,不能让d[s1.length][s2.length],这样index只能取到s1.length-1和s2.length-1
  • 推导公式,关键就在s1[i-1]==s3[i+j-1]这一句,因为是取s1的前i个,那最后一个就是s[i-1]了,这一点要严格按照d[i][j]的定义来

d[i][j] = (d[i-1][j]&&s1[i -1 ]==s3[i+j -1 ]) || (d[i][j-1]&&s2[j-1]==s3[i+j-1])

#代码

package InterleaveString;

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {

        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }

        boolean[][] d = new boolean[s1.length()+1][s2.length()+1];
        d[0][0] = true;

        for (int i = 1; i <= s1.length(); i++) {
            if(s1.charAt(i-1) == s3.charAt(i-1)) {
                d[i][0] = true;
            } else {
                break;
            }
        }

        for (int j = 1; j <= s2.length(); j++) {
            if (s2.charAt(j-1) == s3.charAt(j-1)) {
                d[0][j] = true;
            } else {
                break;
            }
        }

        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                d[i][j] |= d[i - 1][j] && s1.charAt(i-1) == s3.charAt(i + j-1);
                d[i][j] |= d[i][j - 1] && s2.charAt(j-1) == s3.charAt(i + j-1);
            }
        }


        return d[s1.length()][s2.length()];
    }

}
共有 人打赏支持
Finley.Hamilton
粉丝 5
博文 44
码字总数 15431
×
Finley.Hamilton
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: