Description

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.

Example 1:

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

Example 2:

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

Solution

You may considering the string is not always split at the middle.

The tree could be like this:

     great
    /     \
   g       reat
          /    \
         r      eat
                ...

Divide And Conquer (Top to Down)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

func isScramble(s1 string, s2 string) bool {
    if s1 == s2 {
        return true
    }

    length := len(s1)

    // couting letters
    var count [26]int
    for i := 0; i < length; i++ {
        count[s1[i]-'a']++
        count[s2[i]-'a']--
    }

    // Does letters same?
    for i := 0; i < 26; i++ {
        if count[i] != 0 {
            return false
        }
    }

    for k := 1; k < length; k++ {
        if isScramble(s1[k:], s2[k:]) && isScramble(s1[:k], s2[:k]) {
            return true
        }

        // exchange substrings
        if isScramble(s1[k:], s2[:length-k]) && isScramble(s1[:k], s2[length-k:]) {
            return true
        }
    }

    return false
}

Dynamic Programming (Bottom to Up)

Definition dp[l][i][j]:

  • s1[i] start from 'i'
  • s2[j] start from 'j'
  • 'l' is the length of substring, the length in recursive solution.

Initialization dp[1][i][j] = (s1[i] == s2[j] ? true : false).

dp[l][i][j] =
    // isScramble(s1[k:], s2[k:]) && isScramble(s1[:k], s2[:k])
    (dp[k][i][j] && dp[l-k][i+k][j+k]) ||

    // isScramble(s1[k:], s2[:length-k]) && isScramble(s1[:k], s2[length-k:])
    (dp[k][i][j+l-k] && dp[l-k][i+k][j])

k means split the l to two parts, so 0 <= k <= l;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

func isScramble(s1 string, s2 string) bool {
    if len(s1) != len(s2) {
        return false
    }

    length := len(s1)

    dp := make([][][]bool, length+1)
    for i := 0; i <= length; i++ {
        dp[i] = make([][]bool, length)
        for j := 0; j < length; j++ {
            dp[i][j] = make([]bool, length)
        }
    }

    for i := 0; i < length; i++ {
        for j := 0; j < length; j++ {
            dp[1][i][j] = (s1[i] == s2[j])
        }
    }

    for l := 2; l <= length; l++ {
        for i := 0; i < length-l+1; i++ {
            for j := 0; j < length-l+1; j++ {
                if dp[l][i][j] {
                    continue
                }

                for k := 1; k < l && (!dp[l][i][j]); k++ {
                    dp[l][i][j] = (dp[k][i][j] && dp[l-k][i+k][j+k]) ||
                        (dp[k][i][j+l-k] && dp[l-k][i+k][j])
                }
            }
        }
    }

    return dp[length][0][0]
}