文档章节

Interleaving String

Finley.Hamilton
 Finley.Hamilton
发布于 2014/11/22 21:35
字数 371
阅读 586
收藏 1

题目

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

Finley.Hamilton

粉丝 4
博文 45
码字总数 15431
作品 0
广州
Lintcode29 Interleaving String solution 题解

【题目描述】 Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2. 给出三个字符串:s1、s2、s3,判断s3是否由s1和s2交叉构成。 【题目链接...

coderer
2017/05/07
0
0
Live555源代码解读(4)下

[cpp] view plaincopy static ServerMediaSession* createNewSMS(UsageEnvironment& env,char const* fileName, FILE* /fid/) { // Use the file name extension to determine the type of "......

Sean-x
2016/02/24
19
0
C++11 并发编程教程 - Part 2 : 保护共享数据

上一篇文章我们讲到如何启动一些线程去并发地执行某些操作,虽然那些在线程里执行的代码都是独立的,但通常情况下,你都会在这些线程之间使用到共享数据。一旦你这么做了,就面临着一个新的问...

天下杰论
2013/12/29
0
0
论文笔记:Predicting Target Language CCG Supertags Improves Neural Machine Translation

一、文章有什么贡献? 主要共享是提出了一个新的思路,以CCG (Combinatory Categorial Grammar) Supertag的形式将句法信息引入了,NMT(神经机器翻译)的解码器端,对NMT的性能有了一定提高。...

坂本龙一
2017/11/07
0
0
Ember v2.1.0-beta.4 发布

Ember v2.1.0-beta.4 发布,此版本主要是 bug 修复: #12075 [PERF] Avoid creating a run-loop for events that are unhandled. #12260 [BUGFIX] Ensure is completed before is fired. #1......

oschina
2015/09/14
595
2

没有更多内容

加载失败,请刷新页面

加载更多

下一页

HTTPS is easy

HTTPS is easy https://www.troyhunt.com/https-is-easy/ HTTPS is easy! In fact, it's so easy I decided to create 4 short videos around 5 minutes each to show people how to enable ......

openthings
29分钟前
0
0
bugList 2

用户端: 1. 上传文件时,当选择:彩色-A3-双面时,第二个图片有bug 应改为 和第一个图片的类型相同 2. 确认打印时,三个下拉选目前有bug 应改为:根据后台配置的商家,group by计算出不同城...

勇恒
32分钟前
2
0
keras cnn 网咯 mnist 分类

搭建貌似比tf是简单很多。。。。。 from keras.datasets import mnistfrom keras.utils import np_utilsfrom keras.models import Sequentialfrom keras.layers import Dense, Activat......

阿豪boy
35分钟前
0
0
解决 /var/run/nginx.pid failed

nginx: [error] open() "/var/run/nginx.pid" failed (2: No such file or directory) sudo nginx -c /etc/nginx/nginx.conf nginx -s reload...

驛路梨花醉美
36分钟前
0
0
nginx负载均衡-ssl原理-生成ssl密钥对-nginx配置ssl

nginx负载均衡: 1.创建配置文件 vim /usr/local/nginx/conf/vhost/load.conf #添加以下内容: upstream qq_com #名字自定义,借助此模块定义多个IP,后面...

ZHENG-JY
36分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部