Share my 2ms java recursive solution beat 99.53% constantly


  • 0
    J
    public class Solution {
        public boolean isScramble(String s1, String s2) {
            if (s1.equals(s2)) {
                return true;
            }
            int n = s1.length();
            int count1 = 0;
            int count2 = 0;
            int[] map1 = new int[26];
            int[] map2 = new int[26];
            int idx;
            for (int k = 0; k < n - 1; k++) {
                // traversing s1
                idx = s1.charAt(k) - 'a';
                map1[idx]++;
                map2[idx]++;
                count1 += (map1[idx] > 0) ? 1 : -1;
                count2 += (map2[idx] > 0) ? 1 : -1;
                
                // traversing s2
                idx = s2.charAt(k) - 'a';
                map1[idx]--;
                count1 += (map1[idx] < 0) ? 1 : -1;
                
                // backward traversing s2
                idx = s2.charAt(n - 1 - k) - 'a';
                map2[idx]--;
                count2 += (map2[idx] < 0) ? 1 : -1;
                
                if (count1 == 0
                    // first part of s1 match with first part of s2
                    && isScramble(s1.substring(0, k + 1), s2.substring(0, k + 1)) 
                    && isScramble(s1.substring(k + 1), s2.substring(k + 1))
                    || count2 == 0 
                    // first part of s1 match with second part of s2
                    && isScramble(s1.substring(0, k + 1), s2.substring(n - 1 - k)) 
                    && isScramble(s1.substring(k + 1), s2.substring(0, n - 1 - k))) {
                    return true;
                }
            }
            return false;
        }
    }
    

    Any suggestion or analysis would be appreciated. Not quite sure why this is so efficient.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.