leetcode 87. 扰乱字符串

题目描述

给定一个字符串 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

题解

递归,i 作为分割位,分割之后的两部分 s[:i+1], s[i+1:] 可能交换,也可能不交换,所以有两种可能

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func isScramble(s1 string, s2 string) bool {
if s1 == s2 {
return true
}
if !isSame(s1, s2) {
return false
}
n := len(s1)
for i := 1; i < n; i++ {
if isScramble(s1[:i], s2[:i]) && isScramble(s1[i:], s2[i:]) {
return true
}
if isScramble(s1[:i], s2[n-i:]) && isScramble(s1[i:], s2[:n-i]) {
return true
}
}
return false
}

func isSame(s1, s2 string) bool {
hash := make(map[byte]int)
for i := len(s1)-1; i >= 0; i-- {
hash[s1[i]]++
}
for i := len(s2)-1; i >= 0; i-- {
hash[s2[i]]--
if hash[s2[i]] < 0 {
return false
}
}
return true
}