织梦可以做家教网站吗,做网站优化推广,wordpress在后台文章自定义表单,网站建设飠金手指下拉使用下面描述的算法可以扰乱字符串 s 得到字符串 t #xff1a; 如果字符串的长度为 1 #xff0c;算法停止 如果字符串的长度 1 #xff0c;执行下述步骤#xff1a; 在一个随机下标处将字符串分割成两个非空的子字符串。即#xff0c;如果已知字符串 s #xff0c…使用下面描述的算法可以扰乱字符串 s 得到字符串 t 如果字符串的长度为 1 算法停止 如果字符串的长度 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
解题思路
dp[i1][i2][len] 代表 s1[i1,i1len)s2[i2,i2len)是否互为扰乱字符串0代表未判断1和-1分别代表是和否。 状态转移两种情况 i为长度范围是1到 len-1
1.没有交换顺序的直接将s1s2切割为前一段为i长度后一端为len-i长度分别比较s1s2的两个子串如果两个子串也是扰乱字符串当前字符串就满足扰乱字符串的定义。2.交换顺序后将s1切割为前一段为i长度后一端为len-i长度而将s1切割为前一段为len-i长度后一端为i长度将s1的前端和s2的后端作比较s1的后端和s2前端作比较
代码
public class Solution {int [][][] dp;String ss1,ss2;public boolean isScramble(String s1, String s2) {int ns1.length();ss1s1;ss2s2;dpnew int[n][n][n1];return dfs(0,0,n);}public boolean dfs(int i1,int i2,int len){if(dp[i1][i2][len]!0){return dp[i1][i2][len]1;}if(ss1.substring(i1,i1len).equals(ss2.substring(i2,i2len))){dp[i1][i2][len]1;return true;}if(!check(i1,i2,len)){dp[i1][i2][len]-1;return false;}for(int i1;ilen;i){if(dfs(i1, i2, i)dfs(i1i, i2i, len-i)){dp[i1][i2][len]1;return true;}if(dfs(i1, i2len-i, i)dfs(i1i, i2, len-i)){dp[i1][i2][len]1;return true;}}dp[i1][i2][len]-1;return false;}public boolean check(int i1,int i2,int len){int[] checknew int[26];for (int ii1;ii1len;i)check[ss1.charAt(i)-a];for(int ii2;ii2len;i)check[ss2.charAt(i)-a]--;for(int i0;i26;i)if(check[i]!0) return false;return true;}}
