87. 扰乱字符串

题意：

解题思路：

思路：(递归)
1. 初始化判断两个字符长度是否相等，如果不等，则一定不能相互转化；
2. 循环遍历第一个字符串s1
    2.1 如果没有翻转，则分别判断s1,s2的 [s1, n-s1],[s2, n-s2]是否可以相互转化；
    2.2 如果有翻转，则分别判断s1,s2的[s1, n-s2],[s2, n-s1]是否可以相互转化；

PHP代码实现：

class Solution {
    /**
     * @param String $s1
     * @param String $s2
     * @return Boolean
     */
    function isScramble($s1, $s2) {
        if (strlen($s1) != strlen($s2)) return false;
        if ($s1 == $s2) return true;
        $str1 = $s1;
        $str2 = $s2;
        $strArr1 = str_split($str1);
        sort($strArr1);
        $str1 = implode('', $strArr1);
        $strArr2 = str_split($str2);
        sort($strArr2);
        $str2 = implode('', $strArr2);
        if ($str1 != $str2) return false;
        for ($i = 1; $i < strlen($s1); $i++) {
            // great => [g reat, r geat] => [gr eat, rg eat]
            if ($this->isScramble(substr($s1, 0, $i), substr($s2, 0, $i)) 
                && $this->isScramble(substr($s1, $i), substr($s2, $i))) {
                return true;
            }
            if ($this->isScramble(substr($s1, 0, $i), substr($s2, strlen($s2) - $i)) 
                && $this->isScramble(substr($s1, $i), substr($s2, 0, strlen($s2) - $i))) {
                return true;
            }
        }
        return false;
    }
}

GO代码实现：

func isScramble(s1 string, s2 string) bool {
    if s1 == s2 {
        return true
    }
    if len(s1)!=len(s2){
        return false
    }
    var s1Map, s2Map [26]int
    for i := 0; i < len(s1); i++ {
        s1Map[s1[i]-'a']++
        s2Map[s2[i]-'a']++
    }
    for i := 0; i < 26; i++ {
        if s1Map[i] != s2Map[i] {
            return false
        }
    }
    length := len(s1)
    for i := 1; i < len(s1); i++ {
        ls1, rs1 := s1[:i], s1[i:]
        ls2, rs2 := s2[:i], s2[i:]
        nb, mb := s2[length-i:], s2[:length-i]
        if isScramble(ls1, ls2) && isScramble(rs1, rs2) || 
            isScramble(ls1, nb) && isScramble(rs1, mb) {
            return true
        }
    }
    return false
}