使用下面描述的算法可以擾亂字符串 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,i1+len),s2[i2,i2+len)是否互為擾亂字符串,0代表未判斷,1和-1分別代表是和否。
狀態轉移:兩種情況
i為長度,范圍是(1到 len-1)
- 1.沒有交換順序的,直接將s1,s2切割為前一段為i長度,后一端為len-i長度,分別比較s1,s2的兩個子串,如果兩個子串也是擾亂字符串,當前字符串就滿足擾亂字符串的定義。
- 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 n=s1.length();ss1=s1;ss2=s2;dp=new int[n][n][n+1];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,i1+len).equals(ss2.substring(i2,i2+len))){dp[i1][i2][len]=1;return true;}if(!check(i1,i2,len)){dp[i1][i2][len]=-1;return false;}for(int i=1;i<len;i++){if(dfs(i1, i2, i)&&dfs(i1+i, i2+i, len-i)){dp[i1][i2][len]=1;return true;}if(dfs(i1, i2+len-i, i)&&dfs(i1+i, 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[] check=new int[26];for (int i=i1;i<i1+len;i++)check[ss1.charAt(i)-'a']++;for(int i=i2;i<i2+len;i++)check[ss2.charAt(i)-'a']--;for(int i=0;i<26;i++)if(check[i]!=0) return false;return true;}}