leetCode.87. 扰乱字符串

devtools/2024/9/19 0:39:51/ 标签: leetcode, dp, dfs

leetcode.cn/problems/scramble-string/description/" rel="nofollow">leetCode.87. 扰乱字符串

题目思路（该方法以前可以过，现在对时间复杂度的要求严格了许多，不能过去）：
这里显示，能够让我自己后期复习的时候，可以掌握最基本的做法（尽管不能通过全部样例，但至少会一种方法）
dfs
在这里插入图片描述

在这里插入图片描述

代码

// 方案一：暴力递归，会超时，以前会过的，现在时间复杂度要求的跟小了
class Solution {
public:bool isScramble(string s1, string s2) {if (s1 == s2) return true;string str1 = s1, str2 = s2;sort(str1.begin(), str1.end());sort(str2.begin(), str2.end());// 表示拆分翻转后，不相等，表示失败，不匹配if (str1 != str2) return false;// 从1开始，主要是，子节点至少有1个数for (int i = 1; i < s1.size(); i++) {// 根节点不反转，结果返回true,后面就不用验证了if( isScramble(s1.substr(0,i) , s2.substr(0,i)) &&  isScramble(s1.substr(i),s2.substr(i)))return true;// 后面同理根节点翻转，也能返回true也就用户验证了if( isScramble(s1.substr(0,i), s2.substr(s2.size() - i)) && isScramble(s1.substr(i),s2.substr(0,s2.size() - i)))return true;}return false;}
};

时间复杂度o(n^5)

方法二：用dp来做

有状态定义，f[i][j][len]表示s1从i开始，s2从j开始，后面长度为len的字符是否能形成扰乱字符串（互为翻转）

可以参考这个题解
主要还是关注的两个状态：
1.当根节点不翻转，看f[i,j,k]和f[i+k,j+k,len-k]
2.当根节点翻转，看f[i][j+len-k][k]和f[i+k][j][len-k]
这两个状态是否为1

class Solution {
public:bool isScramble(string s1, string s2) {if (s1 == s2) return true;if (s1.size() != s2.size()) return false;int n = s1.size();vector<vector<vector<int>>> f(n, vector<vector<int>>(n,vector<int>(n + 1,0)));// 先处理长度为1的情况for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {if (s1[i] == s2[j]) f[i][j][1] = true;}}// 在处理剩余的情况,依次当有len个长度进行翻转的时候for (int len = 2; len <= n; ++len) {for (int i = 0; i + len <= n; ++i) {for (int j = 0; j + len <= n; ++j) {for (int k = 1; k < len; ++k) { // 表示左边或者右边至少有一个元素bool a = f[i][j][k] && f[i + k][j + k][len - k];bool b = f[i][j + len - k][k] && f[i + k][j][len - k];if (a || b) {f[i][j][len] = true;}}}}}return f[0][0][n];}
};