文档章节

Interleaving String

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

题目

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
博文 44
码字总数 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

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 ⋅ 0

C++11 并发编程教程 - Part 2 : 保护共享数据

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

天下杰论 ⋅ 2013/12/29 ⋅ 0

论文笔记:Predicting Target Language CCG Supertags Improves Neural Machine Translation

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

坂本龙一 ⋅ 2017/11/07 ⋅ 0

播放视频的时候提示 error(1,-2147483648)

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

fbhokzd2jo ⋅ 2014/04/15 ⋅ 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 ⋅ 2

common lisp 的merge

@烟波 你好,想跟你请教个问题:这个是cltl2上merge的描述,能否帮我翻译并解释一下,谢谢。 The merge function determines the relationship between two elements by giving keys extract...

LIGHT-LOGO ⋅ 2014/12/03 ⋅ 3

Teiid 9.0.1 发布,数据虚拟化系统

Teiid 9.0.1 发布了,Teiid是一个数据虚拟化系统,让应用程序使用来自多个异构数据存储的数据。Teiid 可以让你用 JDBC + SQL 来访问企业的任何数据,并可对这些不同源的数据进行联合查询。T...

oschina ⋅ 2016/07/05 ⋅ 0

JTA分布式事务实践

最近一直在研究怎么实现分布式事务,花了不少时间,测试工程启停测试了无数次,最终实现的时候其实也就是写一些配置文件,对于工程代码没什么影响。目前研究还不是很深入,对于全面崩溃恢复如...

引鸩怼孑 ⋅ 2016/04/27 ⋅ 0

LeetCode Question Difficulty Distribution 问题难度和频率分布

Leetcode问题难度和频率分布表 引用自: https://zephyrusara.blogspot.jp/2014/07/leetcode-question-difficulty.html LeetCode Question Difficulty Distribution : Sheet1......

xidiancoder ⋅ 2017/09/10 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

如何优雅的编程——C语言界面的一点小建议

我们鼓励在编程时应有清晰的哲学思维,而不是给予硬性规则。我并不希望你们能认可所有的东西,因为它们只是观点,观点会随着时间的变化而变化。可是,如果不是直到现在把它们写在纸上,长久以...

柳猫 ⋅ 31分钟前 ⋅ 0

从零手写 IOC容器

概述 IOC (Inversion of Control) 控制反转。熟悉Spring的应该都知道。那么具体是怎么实现的呢?下面我们通过一个例子说明。 1. Component注解定义 package cn.com.qunar.annotation;impo...

轨迹_ ⋅ 31分钟前 ⋅ 0

系统健康检查利器-Spring Boot-Actuator

前言 实例由于出现故障、部署或自动缩放的情况,会进行持续启动、重新启动或停止操作。它可能导致它们暂时或永久不可用。为避免问题,您的负载均衡器应该从路由中跳过不健康的实例,因为它们...

harries ⋅ 33分钟前 ⋅ 0

手把手教你搭建vue-cli脚手架-详细步骤图文解析[vue入门]

写在前面: 使用 vue-cli 可以快速创建 vue 项目,vue-cli很好用,但是在最初搭建环境安装vue-cli及相关内容的时候,对一些人来说是很头疼的一件事情,本人在搭建vue-cli的项目环境的时候也是...

韦姣敏 ⋅ 43分钟前 ⋅ 0

12c rman中输入sql命令

12c之前版本,要在rman中执行sql语句,必须使用sql "alter system switch logfile"; 而在12c版本中,可以支持大量的sql语句了: 比如: C:\Users\zhengquan>rman target / 恢复管理器: Release 1...

tututu_jiang ⋅ 57分钟前 ⋅ 0

Nginx的https配置记录以及http强制跳转到https的方法梳理

Nginx的https配置记录以及http强制跳转到https的方法梳理 一、Nginx安装(略) 安装的时候需要注意加上 --with-httpsslmodule,因为httpsslmodule不属于Nginx的基本模块。 Nginx安装方法: ...

Yomut ⋅ 今天 ⋅ 0

SpringCloud Feign 传递复杂参数对象需要注意的地方

1.传递复杂参数对象需要用Post,另外需要注意,Feign不支持使用GetMapping 和PostMapping @RequestMapping(value="user/save",method=RequestMethod.POST) 2.在传递的过程中,复杂对象使用...

@林文龙 ⋅ 今天 ⋅ 0

如何显示 word 左侧目录大纲

打开word说明文档,如下图,我们发现左侧根本就没有目录,给我们带来很大的阅读障碍 2 在word文档的头部菜单栏中,切换到”视图“选项卡 3 然后勾选“导航窗格”选项 4 我们会惊奇的发现左侧...

二营长意大利炮 ⋅ 今天 ⋅ 0

智能合约编程语言Solidity之线上开发工具

工具地址:https://ethereum.github.io/browser-solidity/ 实例实验: 1.创建hello.sol文件 2.调试输出结果

硅谷课堂 ⋅ 今天 ⋅ 0

ffmpeg 视频格式转换

转 Mp4 格式 #> ffmpeg -i input.avi -c:v libx264 output.mp4#> ffmpeg -i input.avi -c:v libx264 -strict -2 output.mp4#> ffmpeg -i input.avi -c:v libx264 -strict -2 -s 1......

Contac ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部