题目出处
87-扰乱字符串-题目出处
题目描述
个人解法
思路：
todo
代码示例：（Java）
todo
复杂度分析
todo
官方解法
87-扰乱字符串-官方解法
方法1：动态规划
思路：
代码示例：（Java）
public class Solution1 {// 记忆化搜索存储状态的数组// -1 表示 false，1 表示 true，0 表示未计算int[][][] memo;String s1, s2;public boolean isScramble(String s1, String s2) {int length = s1.length();this.memo = new int[length][length][length + 1];this.s1 = s1;this.s2 = s2;return dfs(0, 0, length);}// 第一个字符串从 i1 开始，第二个字符串从 i2 开始，子串的长度为 length，是否和谐public boolean dfs(int i1, int i2, int length) {if (memo[i1][i2][length] != 0) {return memo[i1][i2][length] == 1;}// 判断两个子串是否相等if (s1.substring(i1, i1 + length).equals(s2.substring(i2, i2 + length))) {memo[i1][i2][length] = 1;return true;}// 判断是否存在字符 c 在两个子串中出现的次数不同if (!checkIfSimilar(i1, i2, length)) {memo[i1][i2][length] = -1;return false;}// 枚举分割位置for (int i = 1; i < length; ++i) {// 不交换的情况if (dfs(i1, i2, i) && dfs(i1 + i, i2 + i, length - i)) {memo[i1][i2][length] = 1;return true;}// 交换的情况if (dfs(i1, i2 + length - i, i) && dfs(i1 + i, i2, length - i)) {memo[i1][i2][length] = 1;return true;}}memo[i1][i2][length] = -1;return false;}public boolean checkIfSimilar(int i1, int i2, int length) {Map<Character, Integer> freq = new HashMap<Character, Integer>();for (int i = i1; i < i1 + length; ++i) {char c = s1.charAt(i);freq.put(c, freq.getOrDefault(c, 0) + 1);}for (int i = i2; i < i2 + length; ++i) {char c = s2.charAt(i);freq.put(c, freq.getOrDefault(c, 0) - 1);}for (Map.Entry<Character, Integer> entry : freq.entrySet()) {int value = entry.getValue();if (value != 0) {return false;}}return true;}}复杂度分析
考察知识点
收获
Gitee源码位置
87-扰乱字符串-源码
