专栏首页desperate633LintCode 交叉字符串题目分析代码

LintCode 交叉字符串题目分析代码

题目

给出三个字符串:s1、s2、s3,判断s3是否由s1和s2交叉构成

样例 比如 s1 = "aabcc" s2 = "dbbca" 当 s3 = "aadbbcbcac",返回 true. 当 s3 = "aadbbbaccc", 返回 false.

分析

这道题可以用动态规划的思想解决。 dp[i][j]:表示s1的前i个字符和s2的前j个字符是否由交叉构成。 显然对于i+j个字符,要么等于s1的第i个,要么等于s2的第j个

  • 当等于s1的第i个时,那么必须dp[i-1][j]是true,也就是前面i+j-2个字符是由交叉构成的,那么加进来的就为true
  • 同理对于等于s2的第j个也是。 初始条件,当j=0时,那么s1与s3每个字符相等的话,就为true 同样当i=0时,也是一样!

代码

public class Solution {
    /**
     * Determine whether s3 is formed by interleaving of s1 and s2.
     * @param s1, s2, s3: As description.
     * @return: true or false.
     */
    public boolean isInterleave(String s1, String s2, String s3) {
        if(s1.length()+s2.length() != s3.length())
             return false;
         boolean[][] dp = new boolean[s1.length()+1][s2.length()+1];
         dp[0][0] = true;
         
         for(int i=1;i<=s1.length();i++)
             if(s3.charAt(i-1) == s1.charAt(i-1) && dp[i-1][0])
                 dp[i][0] = true;
         
         for(int i=1;i<=s2.length();i++)
             if(s3.charAt(i-1) == s2.charAt(i-1) && dp[0][i-1])
                 dp[0][i] = true;
         
         for(int i=1;i<=s1.length();i++) {
             for(int j=1;j<=s2.length();j++) {
                 if((s3.charAt(i+j-1) == s1.charAt(i-1) && dp[i-1][j]
                         )|| (s3.charAt(i+j-1) == s2.charAt(j-1) &&dp[i][j-1]))
                     dp[i][j] = true;
             }
         }
         
         return dp[s1.length()][s2.length()];
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LintCode 最长公共子序列题目分析代码

    典型的动态规划问题 dp[i][[j]:表示前i个和前j个字符最大LCS 当A[i] = B[i]的时候: 那么显然dp[i][j] = dp[i-1][...

    desperate633
  • LintCode 交叉字符串题目分析代码

    动态规划问题 dp[i][j]:表示前i个和前j 个是否构成 显然当第s3的i+j个字符,就两种可能,一个等于s1,一个等于s2。

    desperate633
  • LintCode 最长上升子序列题目分析

    给定一个整数序列,找到最长上升子序列(LIS),返回LIS的长度。 说明最长上升子序列的定义: 最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的...

    desperate633
  • 【干货】走进神经网络:直观地了解神经网络工作机制

    【导读】1月4日,Mateusz Dziubek发布了一篇基础的介绍神经网络的博文,作者用一种直观的方法来解释神经网络以及其学习过程,作者首先探讨了导致神经网络...

    WZEARW
  • 18.3.8日报

    electron是注册了个c++对象,在node启动的时候,会hook掉原生node的fs对象(asar_init.js和asar.js里实现hook),把文件...

    龙泉寺扫地僧
  • 小程序 · 一周报

    官方称从微信6.7.2客户端版本开始,为便于用户方便使用小程序,web-view组件在全屏模式下,将统一显示导航栏。开发者在全屏模式下,无需再自行绘制 web-...

    极乐君
  • 假如给你一次机会重新选择,计算机专业选C++ 还是Java?

    已经从事软件开发十几年,C++和java跟着做过好多项目,相对来讲跟C++的感情更加深刻些,毕竟被折腾的时间最长印象也最深刻,刚入行一年就跟着做C++项目,开始...

    程序员互动联盟
  • 海康大华RTSP安防摄像头web无插件直播流媒体服务器EasyNVR接入设备显示immediate exit requested问题解决方案

    进入移动互联网时代以来,企业微信公众号已成为除官网以外非常重要的宣传渠道,当3.2亿直播用户与9亿微信用户的势能累加,在微信上开启直播已成为越来越多企业的必然选...

    EasyNVR
  • OutOfMemoryError异常----Java堆溢出

    在Java虚拟机规范的描述中,除了程序计数器外,虚拟机内存的其他几个运行时区域都有发生OutOfMemoryError(下面都叫OOM)异常的肯能,下面就通过...

    令仔很忙
  • 详解Python序列解包(3)

    本文主要介绍调用函数传递参数时序列解包的用法。在调用函数传递参数时,可以在实参序列前加一个星号*进行序列解包,或在实参字典前加两个星号**进行解包,本文介绍第一...

    Python小屋屋主

扫码关注云+社区

领取腾讯云代金券