Why my O(n^2) code gets TLE using a HashMap


  • 0
    J

    I used double for loop to check each substring (0,i) for future use, and was trying to use a hash map to store the strings that I have already checked. So far I am pretty sure that my solution is O(n^2) but why am I getting TLE in the "aaa...........aaabbaaa......aa" test case? Does containsKey() and get() really takes only O(1) time? Thanks.

    public class Solution {
    public int minCut(String s) {
        if (s.length() <= 1) {
            return 0;
        }
        HashMap<String, Integer> palinStr = new HashMap<String, Integer>();
        palinStr.put("", -1);
        for (int i = 1; i <= s.length(); i++) {
            int minimum = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                int current;
                String left = s.substring(0,j);
                String right = s.substring(j,i);
                if (palinStr.containsKey(right) || isPalindrome(right, palinStr)) {
                    current = palinStr.get(right) + palinStr.get(left) + 1;
                    minimum = Math.min(current, minimum);
                }
            }
            palinStr.put(s.substring(0,i), minimum);
        }
        return palinStr.get(s);
    }
    
    public boolean isPalindrome(String s, HashMap<String, Integer> palinStr) {
        if (palinStr.containsKey(s)) {
            return palinStr.get(s) == 0;
        }
        int cursor1 = 0;
        int cursor2 = s.length()-1;
        while (cursor1 < cursor2) {
            if (s.charAt(cursor1) != s.charAt(cursor2)) {
                return false;
            } else if (palinStr.containsKey(s.substring(cursor1 + 1, cursor2))) {
                palinStr.put(s, 0);
                return palinStr.get(s.substring(cursor1 + 1, cursor2)) == 0;
            }
            cursor1 ++;
            cursor2 --;
        }
        palinStr.put(s, 0);
        return true;
    }
    

    }


Log in to reply
 

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