Java: Backtracking solution.


  • 122
    C

    if the input is "aab", check if [0,0] "a" is palindrome. then check [0,1] "aa", then [0,2] "aab".
    While checking [0,0], the rest of string is "ab", use ab as input to make a recursive call.
    enter image description here

    in this example, in the loop of i=l+1, a recursive call will be made with input = "ab".
    Every time a recursive call is made, the position of l move right.

    How to define a correct answer?
    Think about DFS, if the current string to be checked (Palindrome) contains the last position, in this case "c", this path is a correct answer, otherwise, it's a false answer.

    enter image description here

    line 13: is the boundary to check if the current string contains the last element.
    l>=s.length()

    public class Solution {
            List<List<String>> resultLst;
    	    ArrayList<String> currLst;
    	    public List<List<String>> partition(String s) {
    	        resultLst = new ArrayList<List<String>>();
    	        currLst = new ArrayList<String>();
    	        backTrack(s,0);
    	        return resultLst;
    	    }
    	    public void backTrack(String s, int l){
    	        if(currLst.size()>0 //the initial str could be palindrome
    	            && l>=s.length()){
    	                List<String> r = (ArrayList<String>) currLst.clone();
    	                resultLst.add(r);
    	        }
    	        for(int i=l;i<s.length();i++){
    	            if(isPalindrome(s,l,i)){
    	                if(l==i)
    	                    currLst.add(Character.toString(s.charAt(i)));
    	                else
    	                    currLst.add(s.substring(l,i+1));
    	                backTrack(s,i+1);
    	                currLst.remove(currLst.size()-1);
    	            }
    	        }
    	    }
    	    public boolean isPalindrome(String str, int l, int r){
    	        if(l==r) return true;
    	        while(l<r){
    	            if(str.charAt(l)!=str.charAt(r)) return false;
    	            l++;r--;
    	        }
    	        return true;
    	    }
    }
    

  • 8
    J

    Great illustration and explanation!
    I had the same AC solution in c++, 13ms.

    I used a "tmp string vector" throughout the recursion call path, and push it to the "result vector" only if it successfully reach the end of the original string (all partitions are Palindromes).

    class Solution {
    public:
        vector< vector<string> > partition(string s) {
            vector< vector<string> > result;
            vector< string > tmp;
            recurPartition(s, 0, tmp, result);
            return result;
        }
        void recurPartition(string &s, int start, vector<string> &tmp, vector< vector<string> > &result){
            if(start==s.size()){
                result.push_back(tmp);
            }
            for(int i=start+1; i<=s.size();i++){
                if(isPalindrome(s, start, i)){
                    tmp.push_back(s.substr(start, i-start));
                    recurPartition(s, i, tmp, result);
                    tmp.pop_back();
                }
            }
        }
        bool isPalindrome(string &s, int begin, int end){
            int left=begin;
            int right=end-1;
            while(left<right){
                if(s[left++]!=s[right--])
                    return false;
            }
            return true;
        }
    };
    

  • 1
    G

    Can anyone provide a time complexity analysis for this solution?


  • 71

    Thanks for your sharing. This is a little bit cleaner version of your thought.

    public class Solution {
        public List<List<String>> partition(String s) {
           List<List<String>> res = new ArrayList<List<String>>();
           List<String> list = new ArrayList<String>();
           dfs(s,0,list,res);
           return res;
        }
        
        public void dfs(String s, int pos, List<String> list, List<List<String>> res){
            if(pos==s.length()) res.add(new ArrayList<String>(list));
            else{
                for(int i=pos;i<s.length();i++){
                    if(isPal(s,pos,i)){
                        list.add(s.substring(pos,i+1));
                        dfs(s,i+1,list,res);
                        list.remove(list.size()-1);
                    }
                }
            }
        }
        
        public boolean isPal(String s, int low, int high){
            while(low<high) if(s.charAt(low++)!=s.charAt(high--)) return false;
            return true;
        }
        
    }

  • 0
    F

    What's the time complexity of this method? In the dfs(), there is a for loop, which is O(n); isPal() is another O(n); substring() is another O(n); and dfs() is another O(n). So can I say that it's O(n^4) in the worst case?


  • 15

    Roughly,
    T(n)=T(n-1)+T(n-2)+..+T(1)

    T(n+1)=T(n)+T(n-1)+..+T(1)

    T(n+1)=2T(n)

    T(n)=2^n


  • 0
    I

    if(pos==s.length() && list.size()>0) , the condition list.size() > 0 is not really necessary.


  • 0

    Fix that, thank you.


  • 3
    M

    Time complexity is O(n*(2^n)). The function isPalindrome is O(n)


  • 1
    S

    said in Java: Backtracking solution.:

    backTrack

    This is certainly a backtracking solution, but I think we may end up processing the same index multiple times.
    For example, given "aab", we could reach index l=2 via:

    1. a + a -> b
    2. aa -> b
      In that sense, we should use memoization to avoid duplicated calculation. So shouldn't the best solution be DP instead of backtracking?

  • 0
    L

    Why should we remove the last one E of List?

    currLst.remove(currLst.size()-1);
    

    or

    list.remove(list.size()-1);

  • 0

    Just wondering.. in the second graph, should the node contains "aab" be marked as pink cuz "aab" is not a palindrom?


  • 0
    K

    Hi,guys, First of all,great method, voted. Secondly, I am a rookie in programming , when i saw the method in word break II ,i learned the method of memorized search , so i try to use it in this problem, but the efficiency is quite bad,just beat 14%, I wander why it's like this,thanks a lot. ^^
    my codes are as below.

        Map<String,List<List< String> > > map= new HashMap<>();
    
        public List<List<String>> partition(String s) {
            List<List<String>> res = new ArrayList<List<String>>();
            if(s==null || s.equals("")) {
                return res;
            }
            res =  dfs(s,map);
            for(List<String> l: res){
                l.remove(l.size()-1);
            }
            return res;
    
        }
    
        public List<List<String>> dfs(String s, Map<String,List< List<String>>> map){
            if(map.containsKey(s) ){
                return map.get(s);
            }
            List<List<String> > res = new ArrayList<List<String>>();
            LinkedList<String> list= new LinkedList();
            if(s.equals( "") ){
                list.add("");
                res.add(list);
                map.put(s,res);
                return res;
            }
            for(int i =1;i<=s.length();i++){
                String pres= s.substring(0,i);
                if(isPalin(pres ) ){
                    List<List<String>> prelist= dfs(s.substring(i),map );
                    for(List<String> ll : prelist){
                        LinkedList<String> myl= new LinkedList<>(ll);
                        myl.addFirst(pres);
                        res.add(myl);
                    }
                }
            }
            map.put(s,res);
            return res;
        }
    
        public boolean isPalin(String s){
            int i=0,j=s.length()-1;
            while(i<=j){
                if(s.charAt(i++)!=s.charAt(j--) )
                    return false;
            }
            return true;
        }
    

  • 0
    M

    @LathamZ that is how "backtracking" works.


  • 0
    L

    @ming_tsai Thanks, I got it.


  • 9
    G

    Time complexity: O(n*(2^n))
    For a string with length n, there will be (n - 1) intervals between chars.
    For every interval, we can cut it or not cut it, so there will be 2^(n - 1) ways to partition the string.
    For every partition way, we need to check if it is palindrome, which is O(n).
    So the time complexity is O(n*(2^n))
    Correct me if I'm wrong.


  • 0
    H

    @GaoLiaoLiao The total number of recursions is 2^(n-1), this is following the same logic to subsets. But in each recursion, we have a for loop and the function to determine palindrome inside the loop. So I am guessing the time complexity is like O((n^2)(2^n)).


  • 2
    Y
    This post is deleted!

  • 0
    L

    @charlie-yupeng Thanks for your method,I really appreciate your intelligence.


  • 0
    B

    Why ["a", "ab"] not a valid answer?


Log in to reply
 

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