Scramble String

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

Below is one possible representation of A = “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 A and B of the same length, determine if B is a scrambled string of S.

The first argument of input contains a string A.
The second argument of input contains a string B.

Return an integer, 0 or 1:
    => 0 : False
    => 1 : True

1 <= len(A), len(B) <= 50

Input 1:
    A = "we"
    B = "we"

Output 1:
    1

Input 2:
    A = "phqtrnilf"
    B = "ilthnqrpf"
    
Output 2:
    0

Method 1:

DFS + memo

Solution 1:

public class Solution {
    // DO NOT MODIFY THE ARGUMENTS WITH "final" PREFIX. IT IS READ ONLY
    public int isScramble(final String A, final String B) {
        Map<String, Boolean> map = new HashMap<>();
        return helper(A, B, map) ? 1 : 0;
    }
    
    private boolean helper(String A, String B, Map<String, Boolean> map) {
        if (A.equals(B)) {
            return true;
        }
        String key = A + '_' + B;
        if (map.containsKey(key)) {
            return map.get(key);
        }
        boolean found = false;
        int len = A.length();
        for (int i = 1; i < len; i ++) {
            if (
                helper(A.substring(0, i), B.substring(0, i), map) &&
                helper(A.substring(i, len), B.substring(i, len), map) ||
                helper(A.substring(0, i), B.substring(len - i, len), map) &&
                helper(A.substring(i, len), B.substring(0, len - i), map)
            ) {
                found = true;
                break;
            }
        }
        map.put(key, found);
        return found;
    }
}