87. 扰乱字符串
Difficulty: 困难
使用下面描述的算法可以扰乱字符串 s
得到字符串 t
:
- 如果字符串的长度为 1 ,算法停止
- 如果字符串的长度 > 1 ,执行下述步骤:
- 在一个随机下标处将字符串分割成两个非空的子字符串。即,如果已知字符串
s
,则可以将其分成两个子字符串x
和y
,且满足s = x + y
。 - 随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即,在执行这一步骤之后,
s
可能是s = x + y
或者s = y + x
。 - 在
x
和y
这两个子字符串上继续从步骤 1 开始递归执行此算法。
- 在一个随机下标处将字符串分割成两个非空的子字符串。即,如果已知字符串
给你两个 长度相等 的字符串 s1
和 s2
,判断 s2
是否是 s1
的扰乱字符串。如果是,返回 true
;否则,返回 false
。
示例 1:
输入:s1 = "great", s2 = "rgeat" |
示例 2:
输入:s1 = "abcde", s2 = "caebd" |
示例 3:
输入:s1 = "a", s2 = "a" |
提示:
-
-
-
和 由小写英文字母组成
解法一
LeetCode4.16 每日一题,挺有意思记录一下
记忆化搜索,一开始没看题解磨了好一会儿磨出来的,没经过优化,50ms 过了
class Solution { |
优化后的写法,一开始设置了四维状态
class Solution { |
解法二
区间 DP 的写法,其实在前面写记忆化搜索的时候就意识到了这是个区间 DP,所以写完搜索后马上就写出了下面的解法。状态
- 入口:
- 转移:
- 出口:
class Solution { |