87. Scramble String(扰乱字符串)

题目链接：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(扰乱字符串)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。