Simple idea using Recursion+Memoization Java


  • 0
    G

    Could anyone help me analyze running time? I thought my solution is O(n^2), please correct me if it is wrong!! Here is the code.

    public boolean isScramble(String s1, String s2) {
            if(s1.length()!=s2.length())
                return false;
            Map<String, Boolean> memo = new HashMap<String, Boolean>();
            for(Character c : s1.toCharArray()){
                memo.put(""+c+","+c ,true);
            }
            return helper(s1, s2, memo);
        }
        
        private boolean helper(String s1, String s2, Map<String, Boolean> memo){
            if(memo.containsKey(s1+","+s2))
                return memo.get(s1+","+s2);
            if(s1.equals(s2)){
                memo.put(s1+","+s2, true);
                return true;
            }
                
            for(int i=1; i<s1.length(); i++){
                if(helper(s1.substring(0,i), s2.substring(0,i), memo) 
                        && helper(s1.substring(i), s2.substring(i), memo)){
                    memo.put(s1+","+s2, true);
                    return true;
                }else if(helper(s1.substring(0,i), s2.substring(s2.length()-i), memo) 
                        && helper(s1.substring(i), s2.substring(0,s2.length()-i), memo)){
                    memo.put(s1+","+s2, true);
                    return true;
                }
            }
            memo.put(s1+","+s2, false);
            return false;
        }
    

    The basic idea is compare substring of s1 and s2, and use HashMap to store the compared results. For example, s1 = "great", s2 = "rgtae", we divide the problems into "g" "r" and "reat" "gtae", "gr" "rg" "eat" "tae", ... then record <"g,r", false> <"gr,rg",true>...

    The total number of subproblems is O(n), since we have exactly n-1 ways to split the string. The time/subproblem is also O(n), one for loop in helper function. Based on my analysis, the total time complexity is O(n^2).

    Thanks in advance!


Log in to reply
 

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