文档章节

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

粉丝 5
博文 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
播放视频的时候提示 error(1,-2147483648)

用模拟器播放一组视频 其中一个出现 MediaPlayer.MEDIA_INFO_UNKNOWN: error(1,-2147483648) 这样的错误 用中等配置的手机可以播放 低端手机只有声音没有视图 @Override public void surfac...

fbhokzd2jo
2014/04/15
4.6K
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
614
2

没有更多内容

加载失败,请刷新页面

加载更多

零距离接触阿里云时序时空数据库TSDB

概述 最近,Amazon新推出了完全托管的时间序列数据库Timestream,可见,各大厂商对未来时间序列数据库的重视与日俱增。 阿里云TSDB是阿里巴巴集团数据库事业部研发的一款高性能分布式时序时空...

阿里云云栖社区
15分钟前
0
0
OkHttpClient封装

import java.io.BufferedReader; import java.io.InputStream; import java.io.InputStreamReader; import java.util.Map; import java.util.TreeMap; import java.util.Map.Entry; import o......

尘叙缘
16分钟前
1
0
零距离接触阿里云时序时空数据库TSDB

概述 最近,Amazon新推出了完全托管的时间序列数据库Timestream,可见,各大厂商对未来时间序列数据库的重视与日俱增。 阿里云TSDB是阿里巴巴集团数据库事业部研发的一款高性能分布式时序时空...

阿里云官方博客
17分钟前
0
0
centos 7 nginx_install.sh

#!/bin/bashset -eprintf "============开始安装nginx\n"printf "============输入nginx下载url,按Enter默认下载1.14.2版本\n"download_url='';while truedoread down...

偶遇一只小仙女
17分钟前
0
0
数据库高并发下乐观锁的原理

在高并发下,经常需要处理SELECT之后,在业务层处理逻辑,再执行UPDATE的情况。 若两个连接并发查询同一条数据,然后在执行一些逻辑判断或业务操作后,执行UPDATE,可能出现与预期不相符的结...

hansonwong
19分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部