題目鏈接：https://leetcode.com/problems/scramble-string/

思路：

其實最初拿到這道題是沒有思路的，看了大佬們的解釋才明白，

遞歸實現，字符串S1和S2

（1）S1?[0,i) 與S2 [ 0,i) ? && ? S1 [i,len)與?S2 [i,len)

或者 ?

（2）S1 [0,i) 與S2 [len-i,len) ? &&S1?[i,len) 與S2 [0,len-i)

(1)(2)中只要滿足一條為true，該部分就滿足擾亂字符串的要求。

僅僅知道這個思路去遞歸還不行，需要一些優化判斷來減少遞歸的次數。

比如：

int[] letters=new int[26];for(int i=0;i<s1.length();i++){letters[s1.charAt(i)-'a']++;letters[s2.charAt(i)-'a']--;}for(int i=0;i<26;i++){if(letters[i]!=0)return false;}

通過這種方式較快的篩選出不符合條件的遞歸字符串，很巧妙的思路，由于后臺測試實力全是小寫字母

只用了26大小的int類型存儲。

AC 2ms 95% Java:

class Solution {public boolean isScramble(String s1, String s2) {if(s1.equals(s2))return true;int[] letters=new int[26];for(int i=0;i<s1.length();i++){letters[s1.charAt(i)-'a']++;letters[s2.charAt(i)-'a']--;}for(int i=0;i<26;i++){if(letters[i]!=0)return false;}for(int i=1;i<s1.length();i++){if(isScramble(s1.substring(0,i),s2.substring(0,i))&&isScramble(s1.substring(i),s2.substring(i)))return true;if(isScramble(s1.substring(0,i),s2.substring(s2.length()-i))&&isScramble(s1.substring(i),s2.substring(0,s2.length()-i)))return true;}return false;}}

?

總結

以上是生活随笔為你收集整理的87. Scramble String(扰乱字符串)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。