[LeetCode] 87. Scramble String

Problem : https://leetcode.com/problems/scramble-string/

Each character of the string can be considered as a leaf node of the binary tree.

If S2 is scrambled of S1.  There is S1 = S11 + S12 and S2 = S21 + S22.   S21 is scrambled from S11a and S22 is scrambled from S12.

from collections import Counter

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        if not s1:
            return not s2
        
        if Counter(s1) != Counter(s2):
            return False
        
        if s1 == s2:
            return True
        
        for i in range(1, len(s1)):
            s11, s12 = s1[:i], s1[i:]
            s21, s22 = s2[:i], s2[i:]
            
            if self.isScramble(s11, s21) and self.isScramble(s12, s22):
                return True
            
            # flip s2 and compare to s1 substrings again
            s21, s22 = s2[:(len(s1) - i)], s2[(len(s1) - i):]
            
            if self.isScramble(s11, s22) and self.isScramble(s12, s21):
                return True
                  
        return False