跳转至

87. 扰乱字符串

题目描述

使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：

  1. 如果字符串的长度为 1 ，算法停止
  2. 如果字符串的长度 > 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"
输出：true
解释：s1 上可能发生的一种情形是：
"great" --> "gr/eat" // 在一个随机下标处分割得到两个子字符串
"gr/eat" --> "gr/eat" // 随机决定：「保持这两个子字符串的顺序不变」
"gr/eat" --> "g/r / e/at" // 在子字符串上递归执行此算法。两个子字符串分别在随机下标处进行一轮分割
"g/r / e/at" --> "r/g / e/at" // 随机决定：第一组「交换两个子字符串」，第二组「保持这两个子字符串的顺序不变」
"r/g / e/at" --> "r/g / e/ a/t" // 继续递归执行此算法，将 "at" 分割得到 "a/t"
"r/g / e/ a/t" --> "r/g / e/ a/t" // 随机决定：「保持这两个子字符串的顺序不变」
算法终止，结果字符串和 s2 相同，都是 "rgeat"
这是一种能够扰乱 s1 得到 s2 的情形，可以认为 s2 是 s1 的扰乱字符串，返回 true

示例 2：

输入：s1 = "abcde", s2 = "caebd"
输出：false

示例 3：

输入：s1 = "a", s2 = "a"
输出：true

 

提示：

  • s1.length == s2.length
  • 1 <= s1.length <= 30
  • s1 和 s2 由小写英文字母组成

解法

方法一：记忆化搜索

我们设计一个函数 $dfs(i, j, k)$，表示字符串 $s_1$ 从 $i$ 开始长度为 $k$ 的子串是否能变换为字符串 $s_2$ 从 $j$ 开始长度为 $k$ 的子串。如果能变换，返回 true，否则返回 false。那么答案就是 $dfs(0, 0, n)$，其中 $n$ 是字符串的长度。

函数 $dfs(i, j, k)$ 的计算方式如下：

  • 如果 $k=1$，那么只需要判断 $s_1[i]$ 和 $s_2[j]$ 是否相等，如果相等返回 true，否则返回 false；
  • 如果 $k \gt 1$，我们枚举分割部分的长度 $h$，那么有两种情况：如果不交换分割的两个子字符串，那么就是 $dfs(i, j, h) \land dfs(i+h, j+h, k-h)$；如果交换了分割的两个子字符串，那么就是 $dfs(i, j+k-h, h) \land dfs(i+h, j, k-h)$。如果两种情况中有一种情况成立，那么就说明 $dfs(i, j, k)$ 成立，返回 true，否则返回 false。

最后，我们返回 $dfs(0, 0, n)$。

为了避免重复计算，我们可以使用记忆化搜索的方式。

时间复杂度 $O(n^4)$，空间复杂度 $O(n^3)$。其中 $n$ 是字符串的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        @cache
        def dfs(i: int, j: int, k: int) -> bool:
            if k == 1:
                return s1[i] == s2[j]
            for h in range(1, k):
                if dfs(i, j, h) and dfs(i + h, j + h, k - h):
                    return True
                if dfs(i + h, j, k - h) and dfs(i, j + k - h, h):
                    return True
            return False

        return dfs(0, 0, len(s1))

 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
class Solution {
    private Boolean[][][] f;
    private String s1;
    private String s2;

    public boolean isScramble(String s1, String s2) {
        int n = s1.length();
        this.s1 = s1;
        this.s2 = s2;
        f = new Boolean[n][n][n + 1];
        return dfs(0, 0, n);
    }

    private boolean dfs(int i, int j, int k) {
        if (f[i][j][k] != null) {
            return f[i][j][k];
        }
        if (k == 1) {
            return s1.charAt(i) == s2.charAt(j);
        }
        for (int h = 1; h < k; ++h) {
            if (dfs(i, j, h) && dfs(i + h, j + h, k - h)) {
                return f[i][j][k] = true;
            }
            if (dfs(i + h, j, k - h) && dfs(i, j + k - h, h)) {
                return f[i][j][k] = true;
            }
        }
        return f[i][j][k] = false;
    }
}

 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
class Solution {
public:
    bool isScramble(string s1, string s2) {
        int n = s1.size();
        int f[n][n][n + 1];
        memset(f, -1, sizeof(f));
        function<bool(int, int, int)> dfs = [&](int i, int j, int k) -> int {
            if (f[i][j][k] != -1) {
                return f[i][j][k] == 1;
            }
            if (k == 1) {
                return s1[i] == s2[j];
            }
            for (int h = 1; h < k; ++h) {
                if (dfs(i, j, h) && dfs(i + h, j + h, k - h)) {
                    return f[i][j][k] = true;
                }
                if (dfs(i + h, j, k - h) && dfs(i, j + k - h, h)) {
                    return f[i][j][k] = true;
                }
            }
            return f[i][j][k] = false;
        };
        return dfs(0, 0, n);
    }
};

 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
func isScramble(s1 string, s2 string) bool {
    n := len(s1)
    f := make([][][]int, n)
    for i := range f {
        f[i] = make([][]int, n)
        for j := range f[i] {
            f[i][j] = make([]int, n+1)
        }
    }
    var dfs func(i, j, k int) bool
    dfs = func(i, j, k int) bool {
        if k == 1 {
            return s1[i] == s2[j]
        }
        if f[i][j][k] != 0 {
            return f[i][j][k] == 1
        }
        f[i][j][k] = 2
        for h := 1; h < k; h++ {
            if (dfs(i, j, h) && dfs(i+h, j+h, k-h)) || (dfs(i+h, j, k-h) && dfs(i, j+k-h, h)) {
                f[i][j][k] = 1
                return true
            }
        }
        return false
    }
    return dfs(0, 0, n)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function isScramble(s1: string, s2: string): boolean {
    const n = s1.length;
    const f = new Array(n)
        .fill(0)
        .map(() => new Array(n).fill(0).map(() => new Array(n + 1).fill(-1)));
    const dfs = (i: number, j: number, k: number): boolean => {
        if (f[i][j][k] !== -1) {
            return f[i][j][k] === 1;
        }
        if (k === 1) {
            return s1[i] === s2[j];
        }
        for (let h = 1; h < k; ++h) {
            if (dfs(i, j, h) && dfs(i + h, j + h, k - h)) {
                return Boolean((f[i][j][k] = 1));
            }
            if (dfs(i + h, j, k - h) && dfs(i, j + k - h, h)) {
                return Boolean((f[i][j][k] = 1));
            }
        }
        return Boolean((f[i][j][k] = 0));
    };
    return dfs(0, 0, n);
}

 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
33
34
public class Solution {
    private string s1;
    private string s2;
    private int[,,] f;

    public bool IsScramble(string s1, string s2) {
        int n = s1.Length;
        this.s1 = s1;
        this.s2 = s2;
        f = new int[n, n, n + 1];
        return dfs(0, 0, n);
    }

    private bool dfs(int i, int j, int k) {
        if (f[i, j, k] != 0) {
            return f[i, j, k] == 1;
        }
        if (k == 1) {
            return s1[i] == s2[j];
        }
        for (int h = 1; h < k; ++h) {
            if (dfs(i, j, h) && dfs(i + h, j + h, k - h)) {
                f[i, j, k] = 1;
                return true;
            }
            if (dfs(i, j + k - h, h) && dfs(i + h, j, k - h)) {
                f[i, j, k] = 1;
                return true;
            }
        }
        f[i, j, k] = -1;
        return false;
    }
}

方法二：动态规划（区间 DP）

我们定义 $f[i][j][k]$ 表示字符串 $s_1$ 从 $i$ 开始长度为 $k$ 的子串是否能变换为字符串 $s_2$ 从 $j$ 开始长度为 $k$ 的子串。那么答案就是 $f[0][0][n]$，其中 $n$ 是字符串的长度。

对于长度为 $1$ 的子串，如果 $s_1[i] = s_2[j]$，那么 $f[i][j][1] = true$，否则 $f[i][j][1] = false$。

接下来，我们从小到大枚举子串的长度 $k$，从 $0$ 开始枚举 $i$，从 $0$ 开始枚举 $j$，如果 $f[i][j][h] \land f[i + h][j + h][k - h]$ 或者 $f[i][j + k - h][h] \land f[i + h][j][k - h]$ 成立，那么 $f[i][j][k]$ 也成立。

最后，我们返回 $f[0][0][n]$。

时间复杂度 $O(n^4)$，空间复杂度 $O(n^3)$。其中 $n$ 是字符串的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        n = len(s1)
        f = [[[False] * (n + 1) for _ in range(n)] for _ in range(n)]
        for i in range(n):
            for j in range(n):
                f[i][j][1] = s1[i] == s2[j]
        for k in range(2, n + 1):
            for i in range(n - k + 1):
                for j in range(n - k + 1):
                    for h in range(1, k):
                        if f[i][j][h] and f[i + h][j + h][k - h]:
                            f[i][j][k] = True
                            break
                        if f[i + h][j][k - h] and f[i][j + k - h][h]:
                            f[i][j][k] = True
                            break
        return f[0][0][n]

 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
class Solution {
    public boolean isScramble(String s1, String s2) {
        int n = s1.length();
        boolean[][][] f = new boolean[n][n][n + 1];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                f[i][j][1] = s1.charAt(i) == s2.charAt(j);
            }
        }
        for (int k = 2; k <= n; ++k) {
            for (int i = 0; i <= n - k; ++i) {
                for (int j = 0; j <= n - k; ++j) {
                    for (int h = 1; h < k; ++h) {
                        if (f[i][j][h] && f[i + h][j + h][k - h]) {
                            f[i][j][k] = true;
                            break;
                        }
                        if (f[i + h][j][k - h] && f[i][j + k - h][h]) {
                            f[i][j][k] = true;
                            break;
                        }
                    }
                }
            }
        }
        return f[0][0][n];
    }
}

 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
class Solution {
public:
    bool isScramble(string s1, string s2) {
        int n = s1.length();
        bool f[n][n][n + 1];
        memset(f, false, sizeof(f));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                f[i][j][1] = s1[i] == s2[j];
            }
        }
        for (int k = 2; k <= n; ++k) {
            for (int i = 0; i <= n - k; ++i) {
                for (int j = 0; j <= n - k; ++j) {
                    for (int h = 1; h < k; ++h) {
                        if () {
                            f[i][j][k] = true;
                            break;
                        }
                        if (f[i + h][j][k - h] && f[i][j + k - h][h]) {
                            f[i][j][k] = true;
                            break;
                        }
                    }
                }
            }
        }
        return f[0][0][n];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func isScramble(s1 string, s2 string) bool {
    n := len(s1)
    f := make([][][]bool, n)
    for i := range f {
        f[i] = make([][]bool, n)
        for j := 0; j < n; j++ {
            f[i][j] = make([]bool, n+1)
            f[i][j][1] = s1[i] == s2[j]
        }
    }
    for k := 2; k <= n; k++ {
        for i := 0; i <= n-k; i++ {
            for j := 0; j <= n-k; j++ {
                for h := 1; h < k; h++ {
                    if (f[i][j][h] && f[i+h][j+h][k-h]) || (f[i+h][j][k-h] && f[i][j+k-h][h]) {
                        f[i][j][k] = true
                        break
                    }
                }
            }
        }
    }
    return f[0][0][n]
}

 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
function isScramble(s1: string, s2: string): boolean {
    const n = s1.length;
    const f = new Array(n)
        .fill(0)
        .map(() => new Array(n).fill(0).map(() => new Array(n + 1).fill(false)));
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < n; ++j) {
            f[i][j][1] = s1[i] === s2[j];
        }
    }
    for (let k = 2; k <= n; ++k) {
        for (let i = 0; i <= n - k; ++i) {
            for (let j = 0; j <= n - k; ++j) {
                for (let h = 1; h < k; ++h) {
                    if (f[i][j][h] && f[i + h][j + h][k - h]) {
                        f[i][j][k] = true;
                        break;
                    }
                    if (f[i + h][j][k - h] && f[i][j + k - h][h]) {
                        f[i][j][k] = true;
                        break;
                    }
                }
            }
        }
    }
    return f[0][0][n];
}

 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
public class Solution {
    public bool IsScramble(string s1, string s2) {
        int n = s1.Length;
        bool[,,] f = new bool[n, n, n + 1];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++ j) {
                f[i, j, 1] = s1[i] == s2[j];
            }
        }
        for (int k = 2; k <= n; ++k) {
            for (int i = 0; i <= n - k; ++i) {
                for (int j = 0; j <= n - k; ++j) {
                    for (int h = 1; h < k; ++h) {
                        if (f[i, j, h] && f[i + h, j + h, k - h]) {
                            f[i, j, k] = true;
                            break;
                        }
                        if (f[i, j + k - h, h] && f[i + h, j, k - h]) {
                            f[i, j, k] = true;
                            break;
                        }
                    }
                }
            }
        }
        return f[0, 0, n];
    }
}

评论