算法题--字符串置乱变换
image.png
0. 链接
1. 题目
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":
great
/ \
gr eat
/ \ / \
g r e at
/ \
a t
To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".
rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t
We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".
rgtae
/ \
rg tae
/ \ / \
r g ta e
/ \
t a
We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
Example 1:
Input: s1 = "great", s2 = "rgeat"
Output: true
Example 2:
Input: s1 = "abcde", s2 = "caebd"
Output: false
2. 思路1：带备忘录的递归
- 分析题意：唯一需要注意的是，字符串的切分点不一定是中点，可能是任意一点
- 基本想法就是divide and conque，详细过程如下所示
abb和bba是可行的
abb和bab也是可行的
前者是s1[:0+1]=a和s2[2-0:]=a同质， 而剩余部分也同质，切分点下标为0
后者是s1[:1+1]=ab和s2[:1+1]=ba同质，而剩余部分也同质, 切分点下标为1
所以，两个字符串同质，可以分为两种情况:
- (
s1靠左若干个字符 VSs2靠右若干个字符)
and (s1剩余字符 VSs2剩余字符) 满足同质关系， 则s1和s2满足同质关系, 这种情况我称之为交叉同质 - (
s1靠左若干个字符 VSs2靠左若干个字符)
and (s1剩余字符 VSs2剩余字符) 满足同质关系，
则s1和s2满足同质关系, 这种情况我称之为同向同质
上述两种情况，只要有一种满足，就说明两个字符串满足同质关系。
所以很明显，
- 原字符串判断同质的问题，就可以转化为子串之间判断同质的问题
- 切分点从左到右变换的过程中，每次要解决的子问题，有大量重复, 例如
s1=great, s2=rgeat，- 当切分点在
0时, 要比较g和r,reat和geat; - 当切分点在
1时, 要比较gr和rg,eat和eat - 可以看出，当切分点在
1的时候，要解决子问题gr和rg，又少不了比较g和r的操作, 而这个刚好是切分点在0时已经处理过的子问题
所以需要备忘录，来记住曾经处理过切分点处的子问题，备忘录的键，可以用两个子串的起止下标组成的元组来表示。
- 当切分点在
3. 代码
# coding:utf8
class Solution:
def isScramble(self, s1: str, s2: str) -> bool:
memo_dict = dict()
def check(a, b, a_start, a_end, b_start, b_end):
key = (a_start, a_end, b_start, b_end)
if key in memo_dict:
# 历史上已经计算过
return memo_dict[key]
if a[a_start: a_end + 1] == b[b_start: b_end + 1]:
# 两个串完全相等
memo_dict[key] = True
return memo_dict[key]
if a_end - a_start != b_end - b_start:
# 长度不等
memo_dict[key] = False
return memo_dict[key]
if a_end == a_start:
# 串长度为1
memo_dict[key] = (a[a_start] == b[b_start])
return memo_dict[key]
for i in range(a_end - a_start):
# 在每个切分点上逐步检查
left_a_start = a_start
left_a_end = a_start + i
right_a_start = a_start + i + 1
right_a_end = a_end
cross_left_b_start = b_start
cross_left_b_end = b_end - i - 1
cross_right_b_start = b_end - i
cross_right_b_end = b_end
same_left_b_start = b_start
same_left_b_end = b_start + i
same_right_b_start = b_start + i + 1
same_right_b_end = b_end
cross_check = check(a, b, left_a_start, left_a_end, cross_right_b_start, cross_right_b_end) \
and check(a, b, right_a_start, right_a_end, cross_left_b_start, cross_left_b_end)
same_check = check(a, b, left_a_start, left_a_end, same_left_b_start, same_left_b_end) \
and check(a, b, right_a_start, right_a_end, same_right_b_start, same_right_b_end)
memo_dict[key] = cross_check or same_check
if memo_dict[key]:
return True
return False
return check(s1, s2, 0, len(s1) - 1, 0, len(s2) - 1)
def my_test(solution, s1, s2):
print('input: s1={}, s2={}; output: {}'.format(s1, s2, solution.isScramble(s1, s2)))
solution = Solution()
my_test(solution, 'great', 'rgeat')
my_test(solution, 'abcde', 'caebd')
my_test(solution, 'abb', 'bab')
my_test(solution, 'abb', 'bba')
输出结果
input: s1=great, s2=rgeat; output: True
input: s1=abcde, s2=caebd; output: False
input: s1=abb, s2=bab; output: True
input: s1=abb, s2=bba; output: True
4. 结果
image.png
