每日一题——扰乱字符串

2024-02-11 07:59
文章标签 字符串 每日 扰乱

本文主要是介绍每日一题——扰乱字符串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

菜鸡每日一题系列打卡87

每天一道算法题目 

小伙伴们一起留言打卡

坚持就是胜利,我们一起努力!

题目描述(引自LeetCode)

给定一个字符串s1,我们可以把它递归地分割成两个非空子字符串,从而将其表示为二叉树。

下图是字符串s1 = "great"的一种可能的表示形式。

    great/    \gr    eat/ \    /  \
g   r  e   at/ \a   t

在扰乱这个字符串的过程中,我们可以挑选任何一个非叶节点,然后交换它的两个子节点。

例如,如果我们挑选非叶节点"gr",交换它的两个子节点,将会产生扰乱字符串"rgeat"。

    rgeat/    \rg    eat/ \    /  \
r   g  e   at/ \a   t

我们将"rgeat"称作"great"的一个扰乱字符串。

同样地,如果我们继续交换节点"eat"和"at"的子节点,将会产生另一个新的扰乱字符串"rgtae"。

    rgtae/    \rg    tae/ \    /  \
r   g  ta  e/ \t   a

我们将"rgtae"称作"great"的一个扰乱字符串。

给出两个长度相等的字符串s1和s2,判断s2是否是s1的扰乱字符串。

示例 1:
输入: s1 = "great", s2 = "rgeat"
输出: true
示例 2:
输入: s1 = "abcde", s2 = "caebd"
输出: false

题目分析

这道题比较容易想到的方式是递归,基于leetcode测试集提供的s1和s2均由字母组成,且长度比较小时,递归是可行的,而且相对比较容易实现;但当组成s1和s2的字符集变大时,或者长度达到一定规模时,就需要考虑采用动态规划。

在这里,菜鸡给出了两种解法,供大家参考。话不多说,上代码!

代码实现

// 递归
class Solution {public boolean isScramble(String s1, String s2) {// 特殊情况处理if (s1 == null || s2 == null) return s1 == s2;if (s1.length() != s2.length()) return false;// dfsreturn dfs(s1, s2, 0, 0, s1.length());}private boolean dfs(String s1, String s2, int i, int j, int l){// 递归终止条件if (l == 1) return s1.charAt(i) == s2.charAt(j);// 剪枝int[] tmp = new int[26];for (int k = 0; k < l; k++) {tmp[s1.charAt(i + k) - 'a']++;tmp[s2.charAt(j + k) - 'a']--;}for (int c : tmp) if (c != 0) return false;// 递归for (int k = 1; k < l; k++) {if (dfs(s1, s2, i, j, k) && dfs(s1, s2, i + k, j + k, l - k)) return true;if (dfs(s1, s2, i, j + l - k, k) && dfs(s1, s2, i + k, j, l - k)) return true;}// 返回return false;}}
// 动态规划
class Solution {public boolean isScramble(String s1, String s2) {// 特殊情况处理if (s1 == null || s2 == null) return s1 == s2;int n = s1.length();if (n != s2.length()) return false;// 初始化dp数组boolean[][][] dp = new boolean[n][n][n + 1];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {dp[i][j][1] = s1.charAt(i) == s2.charAt(j);}}// 计算dp数组for (int l = 2; l <= n; l++) {for (int i = 0; i <= n - l; i++) {for (int j = 0; j <= n - l; j++) {for (int k = 1; k <= l - 1; k++) {if (dp[i][j][k] && dp[i + k][j + k][l - k]) {dp[i][j][l] = true;break;}if (dp[i][j + l - k][k] && dp[i + k][j][l - k]) {dp[i][j][l] = true;break;}}}}}// 返回结果return dp[0][0][n];}}

代码分析

对代码进行分析,递归方式的时间复杂度为阶乘级别;递归调用占用了大量栈空间,空间复杂度为阶乘级别。

动态规划方式,计算dp数组需要四层for循环,时间复杂度为O(n^4);同时,空间上需要三维数组进行状态存储,空间复杂度为O(n^3)。

执行结果

递归方式的执行结果

动态规划方式的执行结果

注意:上述执行结果的差异受leetcode测试集的限制,并不能客观表现递归方式和动态规划方式之间的差异。

学习 | 工作 | 分享

????长按关注“有理想的菜鸡

只有你想不到,没有你学不到

这篇关于每日一题——扰乱字符串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/699275

相关文章

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

MySQL 获取字符串长度及注意事项

《MySQL获取字符串长度及注意事项》本文通过实例代码给大家介绍MySQL获取字符串长度及注意事项,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 获取字符串长度详解 核心长度函数对比⚠️ 六大关键注意事项1. 字符编码决定字节长度2

Springboot3+将ID转为JSON字符串的详细配置方案

《Springboot3+将ID转为JSON字符串的详细配置方案》:本文主要介绍纯后端实现Long/BigIntegerID转为JSON字符串的详细配置方案,s基于SpringBoot3+和Spr... 目录1. 添加依赖2. 全局 Jackson 配置3. 精准控制(可选)4. OpenAPI (Spri

使用Python实现base64字符串与图片互转的详细步骤

《使用Python实现base64字符串与图片互转的详细步骤》要将一个Base64编码的字符串转换为图片文件并保存下来,可以使用Python的base64模块来实现,这一过程包括解码Base64字符串... 目录1. 图片编码为 Base64 字符串2. Base64 字符串解码为图片文件3. 示例使用注意

golang float和科学计数法转字符串的实现方式

《golangfloat和科学计数法转字符串的实现方式》:本文主要介绍golangfloat和科学计数法转字符串的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望... 目录golang float和科学计数法转字符串需要对float转字符串做处理总结golang float

Python如何判断字符串中是否包含特殊字符并替换

《Python如何判断字符串中是否包含特殊字符并替换》这篇文章主要为大家详细介绍了如何使用Python实现判断字符串中是否包含特殊字符并使用空字符串替换掉,文中的示例代码讲解详细,感兴趣的小伙伴可以了... 目录python判断字符串中是否包含特殊字符方法一:使用正则表达式方法二:手动检查特定字符Pytho

MySQL 字符串截取函数及用法详解

《MySQL字符串截取函数及用法详解》在MySQL中,字符串截取是常见的操作,主要用于从字符串中提取特定部分,MySQL提供了多种函数来实现这一功能,包括LEFT()、RIGHT()、SUBST... 目录mysql 字符串截取函数详解RIGHT(str, length):从右侧截取指定长度的字符SUBST

Python将字符串转换为小写字母的几种常用方法

《Python将字符串转换为小写字母的几种常用方法》:本文主要介绍Python中将字符串大写字母转小写的四种方法:lower()方法简洁高效,手动ASCII转换灵活可控,str.translate... 目录一、使用内置方法 lower()(最简单)二、手动遍历 + ASCII 码转换三、使用 str.tr

Java如何用乘号来重复字符串的功能

《Java如何用乘号来重复字符串的功能》:本文主要介绍Java使用乘号来重复字符串的功能,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java乘号来重复字符串的功能1、利用循环2、使用StringBuilder3、采用 Java 11 引入的String.rep