TLE problem


  • 0
    3

    Hi guys!

    My method to solve this problem is very straightforward and should be easy to understand. In my opinion, my method should be O(n^2) time complexity and O(n) space complexity. However, this method is never been accepted. Can anyone tell me why this is TLE. Here is my code. Thanks in advance.

    public class Solution {
        public int minCut(String s) {
            if(s.length() == 0) return 0;
            List<List<String>> list = new ArrayList<List<String>>();
            helper(list, new ArrayList<String>(), s);
            int min = s.length();
            for(List<String> sublist : list) {
                if(sublist.size() < min) {
                    min = sublist.size();
            }
        }
        return min - 1;
    }
    
    
    public void helper(List<List<String>> list, List<String> tmp, String s) {
        if(s.length() == 0) {
            list.add(new ArrayList<String>(tmp));
            return;
        }
        
        for(int i = 0; i < s.length(); i++) {
            if(isPalindrome(s.substring(0, i + 1))) {
                tmp.add(s.substring(0, i + 1));
                helper(list, tmp, s.substring(i + 1));
                tmp.remove(tmp.size() - 1);
            }
        }
    }
    
    public boolean isPalindrome(String s) {
            int lo = 0;
            int hi = s.length() - 1;
        
            while(lo < hi) {
                if(s.charAt(lo) != s.charAt(hi)) return false;
                lo++;
                hi--;
            }
            return true;
        }
    }

  • 0
    F

    Looks like your solution is just brute force....so you generate all possible palindrome partitions and find the minimum. Brute force solution is not O(n^2) time and O(n) space, but exponential. Try this input: aaaa...aaaa, which has all 'a', you should have better understanding of it.


Log in to reply
 

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