面试算法96:字符串交织
题目
输入3个字符串s1、s2和s3,请判断字符串s3能不能由字符串s1和s2交织而成,即字符串s3的所有字符都是字符串s1或s2中的字符,字符串s1和s2中的字符都将出现在字符串s3中且相对位置不变。例如,字符串"aadbbcbcac"可以由字符串"aabcc"和"dbbca"交织而成。
分析
每步从字符串s1或s2中选出一个字符交织生成字符串s3中的一个字符,那么交织生成字符串s3中的所有字符需要多个步骤。每步既可能从字符串s1中选择一个字符,也可能从字符串s2中选择一个字符,也就是说,每步可能面临两个选择。完成一件事情需要多个步骤,而且每步都可能面临多个选择,这个问题看起来可以用回溯法解决。
这个问题并没有要求列出所有将字符串s1和s2交织得到字符串s3的方法,而只是判断能否将字符串s1和s2交织得到字符串s3。如果能够将字符串s1和s2交织得到字符串s3,那么将字符串s1和s2交织得到字符串s3的方法的数目大于0。这只是判断问题的解是否存在(即判断解的数目是否大于0),因此这个问题更适合应用动态规划来解决。
可以用函数f(i,j)表示字符串s1的下标从0到i的子字符串(记为s1[0…i],长度为i+1)和字符串s2的下标从0到j的子字符串(记为s2[0…j],长度为j+1)能否交织得到字符串s3的下标从0到i+j+1(记为s3[0…i+j+1],长度为i+j+2)的子字符串。f(m-1,n-1)就是整个问题的解。
当s3[i+j+1]和s1[i]相同时,f(i,j)的值等于f(i-1,j)的值。类似地,当s3[i+j+1]和s2[j]相同时,f(i,j)的值等于f(i,j-1)的值。如果s1[i]和s2[j]都和s3[i+j+1]相同,此时只要f(i-1,j)和f(i,j-1)有一个值为true,那么f(i,j)的值为true。
解
public class Test {public static void main(String[] args) {boolean result = isInterleave("aabcc", "dbbca", "aadbbcbcac");System.out.println(result);}public static 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;// 列为0,没有取用s2字符串的数字for (int i = 0; i < s1.length(); i++) {dp[i + 1][0] = s1.charAt(i) == s3.charAt(i) && dp[i][0];}// 行为0,没有取用s1字符串的数字for (int j = 0; j < s2.length(); j++) {dp[0][j + 1] = s2.charAt(j) == s3.charAt(j) && dp[0][j];}for (int i = 0; i < s1.length(); i++) {for (int j = 0; j < s2.length(); j++) {char ch1 = s1.charAt(i);char ch2 = s2.charAt(j);char ch3 = s3.charAt(i + j + 1);// 注意是dp[i + 1][j + 1]dp[i + 1][j + 1] = (ch1 == ch3 && dp[i][j + 1]) || (ch2 == ch3 && dp[i + 1][j]);}}return dp[s1.length()][s2.length()];}
}
相关文章:

面试算法96:字符串交织
题目 输入3个字符串s1、s2和s3,请判断字符串s3能不能由字符串s1和s2交织而成,即字符串s3的所有字符都是字符串s1或s2中的字符,字符串s1和s2中的字符都将出现在字符串s3中且相对位置不变。例如,字符串"aadbbcbcac"可以由…...
什么是Vue.js的响应式系统(reactivity system)?如何实现数据的双向绑定?
Vue.js的响应式系统是指一种能够跟踪数据变化并实时更新相关界面的机制。它是Vue.js框架的核心特性之一。 在Vue.js中,你可以使用数据绑定语法将数据绑定到DOM元素上。当绑定的数据发生变化时,Vue.js会自动监听这些变化并更新相关的DOM元素。 Vue.js实…...
力扣labuladong一刷day52天LRU算法
力扣labuladong一刷day52天LRU算法 文章目录 力扣labuladong一刷day52天LRU算法概念一、146. LRU 缓存思路一:使用双向链表加map来手动实现。思路二:使用LinkedHashMap 概念 LRU的全称为Least Recently Used,翻译出来就是最近最少使用的意思…...

CCNP课程实验-06-EIGRP-Trouble-Shooting
目录 实验条件网络拓朴 环境配置开始排错错误1:没有配置IP地址,IP地址宣告有误错误2:R3配置了与R1不同的K值报错了。错误3:R4上的AS号配置错,不是1234错误4:R2上配置的Key-chain的R4上配置的Key-chain不一致…...

判断完全数-第11届蓝桥杯省赛Python真题精选
[导读]:超平老师的Scratch蓝桥杯真题解读系列在推出之后,受到了广大老师和家长的好评,非常感谢各位的认可和厚爱。作为回馈,超平老师计划推出《Python蓝桥杯真题解析100讲》,这是解读系列的第27讲。 判断完全数&#…...

【Bootstrap5学习 day12】
Bootstrap5 导航 Bootstrap5提供了一种简单快捷的方法来创建基本导航,它提供了非常灵活和优雅的选项卡和Pills等组件。Bootstrap5的所有导航组件,包括选项卡和Pillss,都通过基本的.nav类共享相同的基本标记和样式。 创建基本导航 要创建简单…...

算法训练第五十九天|503. 下一个更大元素 II、42. 接雨水
503. 下一个更大元素 II: 题目链接 给定一个循环数组 nums ( nums[nums.length - 1] 的下一个元素是 nums[0] ),返回 nums 中每个元素的 下一个更大元素 。 数字 x 的 下一个更大的元素 是按数组遍历顺序,这个数字之…...

mysql之数据类型、建表以及约束
目录 一. CRUD 1.1 什么是crud 1.2 select(查询) 1.3 INSERT(新增) 1.4 UPDATE(修改) 1.5 DELETE(删除) 二. 函数 2.1 常见函数 2.2 流程控制函数 2.3聚合函数 三. union与union all 3.1 union 3.2 union all 3.3 具体不同 3.4 结论 四、思维导图 一. CRUD 1.1…...

复试 || 就业day04(2024.01.05)项目一
文章目录 前言线性回归房价预测加载数据数据查看数据拆分数据建模模型的验证、应用模型的评估 总结 前言 💫你好,我是辰chen,本文旨在准备考研复试或就业 💫本文内容来自某机构网课,是我为复试准备的第一个项目 &#…...
华为机试真题实战应用【赛题代码篇】-最小传输时延(附python、C++和JAVA代码实现)
目录 问题描述 输入描述: 输出描述: 知识储备 解题思路 思路一...
C++ 运算符重载
(Operator) 加分 减法 []的重载 #include <iostream> using namespace std;class time1 {public:time1(){shi0;fen0;miao0;}time1(int shi, int fen, int miao){this->shi shi;this->fen fen;this->miao miao;}time1 operator (ti…...

vue3学习 【2】vite起步和开发工具基本配置
vite的简介 官方文档 刚起步学习,所以我们只需要按照官方文档的入门流程即可。推荐阅读一下官网的为什么使用vite vite目前需要的node版本是18,可以参考上一篇文章的安装nvm,用来进行多版本的node管理。 vite安装与使用 npm create vitela…...

计算机创新协会冬令营——暴力枚举题目06
我给大家第一阶段的最后一道题就到这里了,下次得过段时间了。所以这道题简单一点。但是足够经典 下述题目描述和示例均来自力扣:两数之和 题目描述 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target …...

单片机快速入门
参考连接: 安装MinGW-64(在win10上搭建C/C开发环境)https://zhuanlan.zhihu.com/p/85429160MinGW-64; 链接:https://pan.baidu.com/s/1oE1FmjyK7aJPnDC8vASmCg?pwdy1mz 提取码:y1mz --来自百度网盘超级会员V7的分享C…...
Eureka相关问题及答案(2024)
1、什么是Eureka? Eureka是一个由Netflix开发的服务发现(Service Discovery)工具,它是Spring Cloud生态系统中的一个关键组件。服务发现是微服务架构中的一个重要概念,它允许服务实例在启动时注册自己,以便…...

Django 7 实现Web便签
一、效果图 二、会用到的知识 目录结构与URL路由注册request与response对象模板基础与模板继承ORM查询后台管理 三、实现步骤 1. terminal 输入 django-admin startapp the_10回车 2. 注册, 在 tutorial子文件夹settings.py INSTALLED_APPS 中括号添加 "the…...

Jenkins集成部署java项目
文章目录 Jenkins简介安装 Jenkins简介 Jenkins能实时监控集成中存在的错误,提供详细的日志文件和提醒功能,还能用图表的形式形象的展示项目构建的趋势和稳定性。 官网 安装 在官网下载windows版本的Jenkins 但是我点击这里浏览器没有反应࿰…...

FFmpeg之——获取上传视频的尺寸(长、宽)
获取上传视频的尺寸: 获取视频尺寸通常需要借助第三方库FFmpeg。 首先,确保你的系统中已安装了FFmpeg,并且FFmpeg的可执行文件路径已经添加到你的系统环境变量中。 1.官网下载ffmpeg 进入 链接: ffmpeg官网 网址,点击下载wind…...

Ajax学习
文章目录 AjaxAjax 是什么Ajax 经典应用场景Ajax 原理示意图ajax的异步请求的方法ajax的逻辑:应用实例-验证用户名是否存在思路框架图:需求分析: 到数据库去验证用户名是否可用思路框架图大功告成:使用JQuery-Ajax实现上面相同的需求:Ajax Ajax 是什么 AJAX 即"Async…...

排序算法——关于快速排序的详解
目录 1.基本思想 2.基本原理 2.1划分思想 2.2排序过程 (1)选择基准值 (2)分割过程(Partition) (3)递归排序 (4)合并过程 2.3具体实例 2.4实现代码 2.5关键要…...

深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

R 语言科研绘图第 55 期 --- 网络图-聚类
在发表科研论文的过程中,科研绘图是必不可少的,一张好看的图形会是文章很大的加分项。 为了便于使用,本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中,获取方式: R 语言科研绘图模板 --- sciRplothttps://mp.…...