What can I improve upon in this code? Please help


  • 0
    B

    I keep getting the Time Limit Exceeded error. Like the bottom-up case, I too memoize for palindromes and min cuts, but there is something I am missing because of which I see TLE.

    public class Solution {
        public int minCut(String s) {
            if(s.length() == 0) return 0;
            Map<String, Integer> map = new HashMap<>();
            Map<String, Boolean> palindromes = new HashMap<>();
            return helper(s, map, palindromes);
        }
        
        private int helper(String s, Map<String, Integer> map, Map<String, Boolean> pals) {
            if(s.length() == 0 || isPalindrome(s, pals)) {
                return 0;
            }
            
            if(map.containsKey(s)){
                return map.get(s);
            }
            
            int min = Integer.MAX_VALUE;
            for(int index = 1; index < s.length(); index++) {
                String left = s.substring(0, index);
                int leftMin = helper(left, map, pals);
                String right = s.substring(index);
                int rightMin = helper(right, map, pals);
                min = Math.min(min, 1 + leftMin + rightMin);
            }
            
            map.put(s, min);
            return min;
        }
        
        private boolean isPalindrome(String s, Map<String, Boolean> map) {
            if(map.containsKey(s)) {
                return map.get(s);
            }
            
            int left = 0;
            int right = s.length() - 1;
            
            while(left <= right) {
                if(s.charAt(left) != s.charAt(right)) {
                    map.put(s, false);
                    return false;
                }
                left++;
                right--;
            }
            
            map.put(s, true);
            return true;
        }
    }
    

  • 0
    M

    @bhimaraju said in What can I improve upon in this code? Please help:
    Hi, I think your code might be incorrect because you are using HasMap<String,Boolean> to memorize. What if two substrings are equal but they are in the different start and end?Also, I believe your code get extremely dragged down by this part.

    You've already spend a lot of time calling s.substring in every for loop. Not to
    mention you call this for loop recursively.

       for(int index = 1; index < s.length(); index++) {
            String left = s.substring(0, index);
            int leftMin = helper(left, map, pals);
            String right = s.substring(index);
            int rightMin = helper(right, map, pals);
            min = Math.min(min, 1 + leftMin + rightMin);
        }
    

    To improve the code. I suggest to use 2D boolean table instead of HashMap. There are some good solutions at the top you might want to check it up.


Log in to reply
 

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