【Leetcode】87. Scramble String（DFS）（字符串）

男娘i 2022-02-23 14:40 185阅读 0赞

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*.

**Example 1:**

Input: s1 = "great", s2 = "rgeat"
    Output: true

**Example 2:**

Input: s1 = "abcde", s2 = "caebd"
    Output: false

题目大意：

给出两个等长的字符串，问s2是否能够通过s1二叉树的左右枝的交换得出。

解题思路：

我们可以保证s1不动，DFS搜索。s1可以分成前后两个部分s1\_1，s1\_2；但是s2可以多一步树枝交换所以可以分成s2\_1，s2\_2，s2\_3，s2\_4。进行叶子节点的匹配如果相等返回true，其中可以增加一步判断，叶子节点中每个字母数量是否相同。

class Solution {
    private:
        bool valid(string s1, string s2){
            if(s1==s2) return true;
            vector<int> num1(26, 0);
            int n = s1.length();
            for(int i=0;i<n;i++){
                num1[s1[i]-'a']++;
                num1[s2[i]-'a']--;
            }
            for(int i = 0;i<26;i++){
                if(num1[i]!=0) return false;
            }
            for(int i=1;i<n;i++){
                string str1_1 = s1.substr(0,i);
                string str1_2 = s1.substr(i,n-i);
                string str2_1 = s2.substr(0,i);
                string str2_2 = s2.substr(i,n-i);
                string str2_3 = s2.substr(0,n-i);
                string str2_4 = s2.substr(n-i,i);
                if(valid(str1_1, str2_1)&&valid(str1_2, str2_2)) return true;
                if(valid(str1_1, str2_4)&&valid(str1_2, str2_3)) return true;
            }
            return false;
        }
    public:
        bool isScramble(string s1, string s2) {
            return valid(s1, s2);
        }
    };