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 条评论
登录 后参与评论

相关文章

来自专栏书山有路勤为径

包含min函数的栈

LeetCode 155. Min Stack 设计一个栈,支持如下操作,这些操作的算法复杂度需要是常数级,O(1) 1.push(x) : 将元素x压入...

1001
来自专栏python3

python random模块

随机输出一个0~4的数字和range()输出的数字,去比较。猜对了,就是字母,否则是数字

802
来自专栏Jed的技术阶梯

图解冒泡排序

在上面实现的代码中,即使n个数本来就是有序的,也会进行(n-1)次排序(只比较,不交换) 优化:当数组已经有序后,就中断循环

1643
来自专栏Jack-Cui

Day3、Python

题目 输入一行字符,分别统计出其中英文字母、空格、数字和其它字符的个数。 1、程序分析     根据题意可知,需要用到字符串的操作方法。本题中要用到的三...

1770
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题31连续子数组的最大和

题目:输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组和的最大值。要求时间复杂度为O(n) 分析:统计连续子数...

3069
来自专栏Python小屋

Python运算符含义汇总

本文以Python 3.5及其以后的版本为主进行介绍。 运算符功能说明+算术加法,列表、元组、字符串合并与连接-算术减法,集合差集*乘法,序列重复/真除法//求...

3557
来自专栏数据结构与算法

U9249 【模板】BSGS

题目描述 给定a,b,p,求最小的非负整数x 满足a^x≡b(mod p) 若无解 请输出“orz” 输入输出格式 输入格式: 三个整数,分别为a,b,p 输出...

3487
来自专栏前端儿

前缀式计算

输入有多组测试数据,每组测试数据占一行,任意两个操作符之间,任意两个操作数之间,操作数与操作符之间都有一个空格。输入的两个操作数可能是小数,数据保证输入的数都是...

1451
来自专栏desperate633

LintCode 完美平方题目分析代码

给一个正整数 n, 找到若干个完全平方数(比如1, 4, 9, ... )使得他们的和等于 n。你需要让平方数的个数最少。

882
来自专栏owent

最长单调子序列 复杂度nlog(n)

761

扫码关注云+社区

领取腾讯云代金券