共计 2344 个字符，预计需要花费 6 分钟才能阅读完成。
一个字符串能够分解成多种二叉树构造。如果 str 长度为 1，认为不可合成。如果 str 长度为 N（N > 1）, 左局部长度可 认为 1 ~ N – 1，剩下的为右局部的长度。左局部和右局部都能够依照同样的逻辑，持续合成。造成的所有构造都是 str 的二叉树构造。
比方，字符串“abcd”，能够分解成一下五种构造：
任何一个 str 的二叉树构造中，如果两个节点有独特的父节点，那么这两个节点能够替换位
置，这两个节点叫作一个替换组。一个构造会有很多替换组，每个替换组都能够抉择进行交
换或者不替换，最终造成一个新的构造，这个新构造所代表的字符串叫作 str 的旋变字符串。
比方，在下面的构造五中，替换组有 a 和 b、ab 和 c、abc 和 d。如果让 a 和 b 的组替换；让 ab 和
c 的组不交 换；让 abc 和 d 的组替换，造成的构造如图
这个新构造所代表的字符串为 ”dbac”，叫作 ”abcd” 的旋变字符串。也就是说，一个字符串
str 的旋变字符串是十分多的，str 能够造成很多种构造，每一种构造都有很多替换组，每
一个替换组都能够抉择替换或者不替换，造成的每一个新的字符串都叫 str 的旋变字符串。
给定两个字符串 str1 和 str2，判断 str2 是不是 str1 的旋变字符串。
解法一：暴力递归
剖析：
str2 是 str1 的旋变字符串必须满足一下条件：
- len(str1) == len(str2)
- str1 和 str2 的字符品种必须雷同。
- str1 和 str2 的每种字符的个数必须雷同。
依据以上三个条件，咱们能够写一个过滤器。
def valid(str1, str2):
if len(str1) != len(str2): return False
map1 = {}
for i in range(len(str1)):
map1[str1[i]] = map1.get(str1[i], 0) + 1
for i in range(len(str2)):
num = map1.get(str2[i], 0)
num -= 1
if num < 0: return False
map1[str2[i]] = num
return True尝试模型是：范畴上尝试
判断 $str[L_1…R_1]$ 和 $str[L_2…R_2]$ 是不是互为旋变字符串。
此种尝试计划：有四个参数：$L_1,R_1,L_2,R_2$
依据上边过滤器的条件，咱们晓得 $str[L_1…R_1]$ 和 $str[L_2…R_2]$ 要是互为旋变字符串，长度必须相等。因而，咱们能够将将参数压缩成三个：$L_1,L_2,K$，k 是 str1 的长度。
$f(L_1,L_2,K)$ 示意 判断 $str[L_1…K+L_1]$ 和 $str[L_2…K+L_2]$ 是不是互为旋变字符串。
最终返回后果：f(0, 0, len(arr) – 1)
Base case
- 如果 k ==1 只有一个字符，只有 $str1[L_1]= str2[L_2]$
如下图：第一刀在 str 中每一个地位进行尝试，每一刀分隔出的两局部进行比对（调用子过程），须要替换后再比对（调用子过程）。
只有有一部分是互为旋变字符串，就返回 true。否则持续尝试第二刀，第三刀 …
def is_scramble(str1, str2):
if not str1 and not str2: return True
if (not str1 and str2) or (str1 and not str2): return False
if str1 == str2: return True
if not valid(str1, str2): return False
return f(str1, str2, 0, 0, len(str1))
def f(str1, str2, l1, l2, k):
if k == 1: return str1[l1] == str2[l2]
for i in range(1, k):
res = (f(str1, str2, l1, l2, i) and f(str1, str2, l1 + i, l2 + i, k - i)) or \
(f(str1, str2, l1, l2 + k - i, i) and f(str1, str2, l1 + i, l2, k - i))
if res: return True
return False解法二：动静布局
- $k \in (1,n] $
- $L_1,L_2 \in(0,n)$
本地依赖关系不好梳理，然而原问题的 k，和依赖的子问题的 k’的关系是：k‘< k。所以在填充以后层数据时，只依赖下边层的数据，不依赖本次层数据。dp 表填充程序，从下向上填写。
base case 是 k ==1 时，$dp[1][l_1][l_2] = str1[l_1] == str2[l_2]$
def is_scramble2(str1, str2):
if not str1 and not str2: return True
if (not str1 and str2) or (str1 and not str2): return False
if str1 == str2: return True
if not valid(str1, str2): return False
n = len(str1)
dp = []
for i in range(n + 1):
dp.append([[False] * n for _ in range(n)])
for l1 in range(n):
for l2 in range(n):
dp[1][l1][l2] = str1[l1] == str2[l2]
for k in range(2, n + 1):
for l1 in range(0, n - k + 1):
for l2 in range(0, n - k + 1):
for i in range(1, k):
if (dp[i][l1][l2] and dp[k - i][l1 + i][l2 + i]) or \
(dp[i][l1][l2 + k - i] and dp[k - i][l1 + i][l2]):
dp[k][l1][l2] = True
break
return dp[n][0][0]本文由 mdnice 多平台公布
