Leetcode 87 Scramble String

思路：我成功地写出了如果只修改一次的话，判断是否是scramble string的方法。但很可惜，这边修改的节点可以是多个，我觉得我这种方法继续写下去应该是可以实现题目要求的，但是我想了好久，不会哈哈哈。我猜应该用recursive的方法来继续写下去？我也不太确定。但是我真的是太不喜欢recursive方法，哎但是，好像dfs，dp都和recursion有着一点关系。真得好好练练。我看了high votes answer，发现人家也是recursive的方法。真的我看懂他这个代码都花了一个多小时吧。烦死了，真的是花时间。其实我感觉自己还没有理解透他的代码。我看是看得懂，也明白为什么要这样recursion。我指的没理解透是我没搞清楚他怎么理出这样一种recursive的方法。他是从哪个点切入的，才发现可以用这种方式解题。就是要从他的code反推，看他是怎么发现这样一种思路的。关于这一点我还没搞透。所以这一题我还是标记为attempted吧，希望以后题目做多了再回去看这道题，可以豁然开朗。下面我给出他的代码，以及其背后的思路。以下思路取自：https://leetcode.wang/leetCode-87-Scramble-String.html

思路：
开始的时候，由于给出的图示很巧都是平均分的，我以为只能平均分字符串，看了这里，明白其实可以任意位置把字符串分成两部分，这里需要注意一下。

这道题很容易想到用递归的思想去解，假如两个字符串 great 和 rgtae。考虑其中的一种切割方式。

第 1 种情况：S1 切割为两部分，然后进行若干步切割交换，最后判断两个子树分别是否能变成 S2 的两部分。

第 2 种情况：S1 切割并且交换为两部分，然后进行若干步切割交换，最后判断两个子树是否能变成 S2 的两部分。

上边只是一种切割方式（以e为切割点，切割点为2，因为indexof（e）= 2），这边只是展示一下正确的切割点，但在真实的情况下，我们需要从0开始遍历所有的切割点。
代码：

public boolean isScramble(String s1, String s2) {if (s1.length() != s2.length()) {return false;}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']--;}//如果两个字符串的字母出现不一致直接返回 falsefor (int i = 0; i < 26; i++) {if (letters[i] != 0) {return false;}}//遍历每个切割位置for (int i = 1; i < s1.length(); i++) {//对应情况 1 ，判断 S1 的子树能否变为 S2 相应部分if (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) {return true;}//对应情况 2 ，S1 两个子树先进行了交换，然后判断 S1 的子树能否变为 S2 相应部分if (isScramble(s1.substring(i), s2.substring(0, s2.length() - i)) &&isScramble(s1.substring(0, i), s2.substring(s2.length() - i)) ) {return true;}}return false; }

最后我还是想展示一下我残缺的代码，就是只需修改一次的。毕竟写都写了，po一下还是要的哈哈哈。

class Solution {public boolean isScramble(String s1, String s2) {if(s1.length() == 1){return s1.equals(s2); }// get all the possible non-leaf nodes(string)int len1 = s1.length();List<String> list = new ArrayList();List<String> resList = new ArrayList();for(int i = 0; i < len1 - 1; i++){for(int j = i + 1; j < len1; j++){list.add(s1.substring(i,j+1));}}// for each non-ledf node, compute its all possible scramble stringsfor(int i = 0; i < list.size(); i++){String s = list.get(i);for(int j = 0; j < s.length(); j++){int idx = s1.indexOf(s);String trans = s.substring(j+1) + s.substring(0,j+1);String completeTrans = s1.substring(0,idx) + trans + s1.substring(idx+trans.length()) ;resList.add(completeTrans);}}// judge if s2 is a valid scramble string of s1return resList.contains(s2);} }

总结：

两个字符相减代表其ascii码相减

好好看好好学好好理解recursive methods

总结

以上是生活随笔为你收集整理的Leetcode 87 Scramble String的全部内容，希望文章能够帮你解决所遇到的问题。

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