Go Java算法之交错字符串示例详解

目录
  • 交错字符串
  • 方法一:动态规划(Java)
  • 方法一:动态规划(GO)

交错字符串

给定三个字符串 s1、s2、s3,请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下,其中每个字符串都会被分割成若干 非空 子字符串:

s = s1 + s2 + ... + sn

t = t1 + t2 + ... + tm

|n - m| <= 1

交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

注意:a + b 意味着字符串 a 和 b 连接。

  • 示例 1:

输入:s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"

输出:true

  • 示例 2:

输入:s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"

输出:false

  • 示例 3:

输入:s1 = "", s2 = "", s3 = ""

输出:true

提示:

0 <= s1.length, s2.length <= 100

0 <= s3.length <= 200

s1、s2、和 s3 都由小写英文字母组成

方法一:动态规划(Java)

状态方程:

边界 1:dp[0][0] = true;

边界 2:if i=0 : dp[0]dp[j] = s2[0-j) equals s3[0,j) 遇到 false 后面可以直接省略

边界 3:if j=0 : dp[i]dp[0] = s1[0-i) equals s3[0,i) 遇到 false 后面可以直接省略

其他情况,到达(i,j)可能由(i-1,j)点向下一步,选择 s1[i-1] 到达;也可能由 (i,j-1) 点向右一步,选择 s2[j-1] 到达;

dp[i,j] = (dp[i-1][j] &&s3[i+j-1] == s1[i-1]) || (dp[i][j-1] && s3[i+j-1] == s2[j-1])

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length(), m = s2.length(), t = s3.length();
        if (n + m != t) {
            return false;
        }
        boolean[][] f = new boolean[n + 1][m + 1];
        f[0][0] = true;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                int p = i + j - 1;
                if (i > 0) {
                    f[i][j] = f[i][j] || (f[i - 1][j] && s1.charAt(i - 1) == s3.charAt(p));
                }
                if (j > 0) {
                    f[i][j] = f[i][j] || (f[i][j - 1] && s2.charAt(j - 1) == s3.charAt(p));
                }
            }
        }
        return f[n][m];
    }
}

时间复杂度:O(m*n)

空间复杂度:O(m*n)

方法一:动态规划(GO)

具体的方法已经在上文中表述,详情请看上文内容。

dp[i][j]含义s1的前i个字符,s2前j个字符,能否组成s3前i+j个字符,能的话填写字符串,否为空字符串

状态转移方程:上方不为空字符串并且s1当前字符等于s3当前字符,则字符串等于上方字符串+s1当前字符 左侧不为空字符串并且s2当前字符等于s3当前字符,则字符串等于左侧字符串+s2当前字符

func isInterleave(s1 string, s2 string, s3 string) bool {
    m, n := len(s1), len(s2)
    if m + n != len(s3) { //长度不等肯定不能组成
        return false
    }
    dp := make([][]string, m+1) //dp[i][j]含义为s1的前i个字符,s2前j个字符,能否组成s3前i+j个字符,能的话填写字符串
    for i:=0; i<=m; i++ {
        dp[i] = make([]string, n+1)
    }
    for i:=1; i<=m; i++ { //s2字符串为空的情况
        if s1[:i] == s3[:i] {
            dp[i][0] = s1[:i]
        }
    }
    for i:=1; i<=n; i++ { //s1字符串为空的情况
        if s2[:i] == s3[:i] {
            dp[0][i] = s2[:i]
        }
    }
    for i:=1; i<=m; i++ {
        for j:=1; j<=n; j++ {
            if dp[i-1][j] != "" && s1[i-1] == s3[i+j-1] { //上方字符串符合并且s1当前字符和s3字符相等,
                dp[i][j] = dp[i-1][j] + string(s1[i-1])   //则当前状态等于上方字符串+s1当前字符
            }
            if dp[i][j-1] != "" && s2[j-1] == s3[i+j-1] { //左侧字符串符合并且s2当前字符和s3字符相等
                dp[i][j] = dp[i][j-1] + string(s2[j-1])   //则当前状态等于左侧字符串+s2当前字符
            }
        }
    }
    if dp[m][n] == s3 { //右下角字符串是否等于s3,等于则能合并出,否则不能
        return true
    }
    return false
}

时间复杂度:O(m*n)

空间复杂度:O(m*n)

以上就是Go Java算法之交错字符串示例详解的详细内容,更多关于Go Java算法交错字符串的资料请关注我们其它相关文章!

(0)

相关推荐

  • Java实现全排列的三种算法详解

    目录 算法一 算法二 算法三 算法一 基于递归与回溯实现.在排列1,2,3的时候,先由3向上回溯到2发现没有其他可能的情况,再回溯到1,排列为1,3,2再向上回溯到存在其他情况时,即根节点然后再排列以2为第一位的情况,重复上述过程将所有可能结果全部放入res中. 代码: import java.util.ArrayList; import java.util.List; public class h618_1 { static List<List<Integer>> res = n

  • Java 常见的限流算法详细分析并实现

    目录 为什么要限流 限流算法 计数器限流 漏桶限流 令牌桶限流 为什么要限流 在保证可用的情况下尽可能多增加进入的人数,其余的人在排队等待,或者返回友好提示,保证里面的进行系统的用户可以正常使用,防止系统雪崩. 限流算法 限流算法很多,常见的有三类,分别是 计数器算法 .漏桶算法.令牌桶算法 . (1)计数器:           在一段时间间隔内,处理请求的最大数量固定,超过部分不做处理. (2)漏桶:           漏桶大小固定,处理速度固定,但请求进入速度不固定(在突发情况请求过多时

  • golang常用加密解密算法总结(AES、DES、RSA、Sha1、MD5)

    目录 关于加密解密 AES DES RSA MD5 Sha1 Base64 在项目开发过程中,当操作一些用户的隐私信息,诸如密码.帐户密钥等数据时,往往需要加密后可以在网上传输.这时,需要一些高效地.简单易用的加密算法加密数据,然后把加密后的数据存入数据库或进行其他操作:当需要读取数据时,把加密后的数据取出来,再通过算法解密. 关于加密解密 当前我们项目中常用的加解密的方式无非三种. 对称加密, 加解密都使用的是同一个密钥, 其中的代表就是AES.DES 非对加解密, 加解密使用不同的密钥, 其

  • Go实现分布式唯一ID的生成之雪花算法

    目录 背景: 特性: 雪花算法: 分布式唯一ID的生成 背景: 在分布式架构下,唯一序列号生成是我们在设计一个尤其是数据库使用分库分表的时候会常见的一个问题 特性: 全局唯一,这是基本要求,不能出现重复数字类型,趋势递增,后面的ID必须比前面的大长度短,能够提高查询效率,这也是从MySQL数据库规范出发的,尤其是ID作为主键时**信息安全,**如果ID连续生成,势必会泄露业务信息,所以需要无规则不规则高可用低延时,ID生成快,能够扛住高并发,延时足够低不至于成为业务瓶颈. 雪花算法: ​ sno

  • Go 加密解密算法小结

    目录 前言 md5 hmac sha1 AES ECB模式 CBC模式 CRT模式 CFB模式 OFB模式 RSA加密 参考: 前言 加密解密在实际开发中应用比较广泛,常用加解密分为:“对称式”.“非对称式”和”数字签名“. 对称式:对称加密(也叫私钥加密)指加密和解密使用相同密钥的加密算法.具体算法主要有DES算法,3DES算法,TDEA算法,Blowfish算法,RC5算法,IDEA算法. 非对称加密(公钥加密):指加密和解密使用不同密钥的加密算法,也称为公私钥加密.具体算法主要有RSA.E

  • 详解Java中Dijkstra(迪杰斯特拉)算法的图解与实现

    目录 简介 工作过程 总体思路 实现 小根堆 Dijsktra 测试 简介 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等.注意该算法要求图中不存在负权边.对应问题:在无向图G=(V,E)中,假设每条边E(i)的长度W(i),求由顶点V0到各节点的最短路径. 工作过

  • Go Java算法之交错字符串示例详解

    目录 交错字符串 方法一:动态规划(Java) 方法一:动态规划(GO) 交错字符串 给定三个字符串 s1.s2.s3,请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的. 两个字符串 s 和 t 交错 的定义与过程如下,其中每个字符串都会被分割成若干 非空 子字符串: s = s1 + s2 + ... + sn t = t1 + t2 + ... + tm |n - m| <= 1 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 +

  • Go Java算法之同构字符串示例详解

    目录 同构字符串 方法一:哈希表(Java) 方法一:哈希表(Go) 同构字符串 给定两个字符串 s 和 t ,判断它们是否是同构的. 如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的. 每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序.不同字符不能映射到同一个字符上,相同字符只能映射到同一个字符上,字符可以映射到自己本身. 示例 1: 输入:s = "egg", t = "add" 输出:true 示例 2: 输入:s = &

  • Go Java算法之单词规律示例详解

    目录 单词规律 方法一:哈希表(Java) 方法一:哈希表(GO) 单词规律 给定一种规律 pattern 和一个字符串 s ,判断 s 是否遵循相同的规律. 这里的 遵循 指完全匹配,例如, pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律. 示例1: 输入: pattern = "abba", s = "dog cat cat dog" 输出: true 示例 2: 输入:pattern = "abba"

  • Go Java算法之解码方法示例详解

    目录 解码方法 方法一:动态规划(Java) 方法二:动态规划——优化(go) 解码方法 一条包含字母 A-Z 的消息通过以下映射进行了 编码 : 'A' -> "1" 'B' -> "2" ... 'Z' -> "26" 要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法).例如,"11106" 可以映射为: "AAJF" ,将消息分组为 (1 1 1

  • Go Java算法之单词搜索示例详解

    目录 单词搜索 算法:DFS回溯(Java) 算法:DFS回溯(Go) 单词搜索 给定一个 m x n 二维字符网格 board 和一个字符串单词 word .如果 word 存在于网格中,返回 true :否则,返回 false . 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格.同一个单元格内的字母不允许被重复使用. 示例 1: 输入:board = [["A","B","C",&quo

  • Go Java算法之累加数示例详解

    目录 累加数 方法一:穷举法(java) 方法二:深度优先遍历(go) 累加数 累加数 是一个字符串,组成它的数字可以形成累加序列. 一个有效的 累加序列 必须 至少 包含 3 个数.除了最开始的两个数以外,序列中的每个后续数字必须是它之前两个数字之和. 给你一个只包含数字 '0'-'9' 的字符串,编写一个算法来判断给定输入是否是 累加数 .如果是,返回 true :否则,返回 false . 说明:累加序列里的数,除数字 0 之外,不会 以 0 开头,所以不会出现 1, 2, 03 或者 1

  • Go Java算法之找不同示例详解

    目录 找不同 方法一:计数(Java) 方法二:求和(Go) 找不同 给定两个字符串 s 和 t ,它们只包含小写字母. 字符串 t 由字符串 s 随机重排,然后在随机位置添加一个字母. 请找出在 t 中被添加的字母. 示例 1: 输入:s = "abcd", t = "abcde" 输出:"e" 解释:'e' 是那个被添加的字母. 示例 2: 输入:s = "", t = "y" 输出:"y&q

  • Go Java算法猜数字游戏示例详解

    目录 猜数字游戏 方法一:遍历(Java) 方法一:遍历(Go) 猜数字游戏 你在和朋友一起玩 猜数字(Bulls and Cows)游戏,该游戏规则如下: 写出一个秘密数字,并请朋友猜这个数字是多少.朋友每猜测一次,你就会给他一个包含下述信息的提示: 猜测数字中有多少位属于数字和确切位置都猜对了(称为 "Bulls",公牛), 有多少位属于数字猜对了但是位置不对(称为 "Cows",奶牛).也就是说,这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字. 给

  • Go java 算法之括号生成示例详解

    目录 括号生成 方法一:深度优先遍历(java) 方法一:深度优先遍历(go) 括号生成 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合. 示例 1: 输入:n = 3 输出:["((()))","(()())","(())()","()(())","()()()"] 示例 2: 输入:n = 1 输出:["()"] 提示: 1 <=

  • Java 数据结构算法Collection接口迭代器示例详解

    目录 Java合集框架 Collection接口 迭代器 Java合集框架 数据结构是以某种形式将数据组织在一起的合集(collection).数据结构不仅存储数据,还支持访问和处理数据的操作 在面向对象的思想里,一种数据结构也被认为是一个容器(container)或者容器对象(container object),它是一个能存储其他对象的对象,这里的其他对象常被称为数据或者元素 定义一种数据结构从实质上讲就是定义一个类.数据结构类应该使用数据域存储数据,并提供方法支持查找.插入和删除等操作 Ja

随机推荐