Leetcode Scramble String 搜索乱序字符

Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

一看样子就知道使用递归无疑了。

主要卡我时间最长的是递归的时候需要交叉递归的，因为根的两个子树以及下面的所有子树都是可以调换的。

思路：

1 检查长度是否一样，不一样就返回false

2 检查当前两个字符是否为乱序，但是所有字符数相等，检查有两个方法： 1） 使用hash表 2）操作字符string排序比较；这里计算就相当于剪枝了，没有这一步会超时的。

3 逐个字符分隔成两个子树，然后递归，注意s1和s2是可以交叉递归的。

好像字符串和一般原始数据一样快，直接操作字符串string的速度很快，比如本题的直接操作字符串的速度也很快。
不过注意如果使用fixedTable为256，即假设为256个ascII码，那么就会比假设为26个小写字符的速度慢上一倍。所以要搞清楚题目要求，根据题目设置hash表

本题也可以使用三维动态规划法，leetcode上有几个列子都是使用动态规划法的。

LeetCode上的例子一般都很好，但是这次例外了，这些动态规划法的例子并不好，因为本题使用动态规划法增加了空间复杂度，甚至时间复杂度，而且实际运行时间比递归剪枝法慢。

下面是使用hash表，利用四点定位递归的程序。

	vector
  
    fixedTable;
	vector
   
     countTable; bool isScramble2(string s1, string s2) { if (s1.length() != s2.length()) return false; return scrambleRecur(s1,s2,0,s1.length()-1,0,s2.length()-1); } bool scrambleRecur(string &s1, string &s2, int begin1, int back1, int begin2, int back2) { if (begin1 > back1 || (begin1==back1 && s1[begin1]==s2[begin2])) return true; fixedTable.clear(); fixedTable.resize(26); countTable.clear(); countTable.resize(26); //有重复的时候需要特殊处理 for (int i = begin1; i <= back1; i++) //例如："abab", "bbaa" { fixedTable[s1[i]-'a']++; } for (int i = begin2; i <= back2; i++) { countTable[s2[i]-'a']++; if (fixedTable[s2[i]-'a'] < countTable[s2[i]-'a']) return false; } //注意：不要写成i<=back-begin，因为递归最重要的原则：子递归必定要比原问题要小，否则就会无限递归，内存溢出了。 for (int i = 0; i < back1-begin1; i++) { if (scrambleRecur(s1,s2,begin1,begin1+i,begin2, begin2+i) &&scrambleRecur(s1,s2,begin1+i+1,back1,begin2+i+1,back2) ||scrambleRecur(s1,s2,begin1,begin1+i, back2-i,back2) &&scrambleRecur(s1,s2,begin1+i+1,back1,begin2,back2-i-1)) return true; } return false; }