Concise Java solution


  • 7
    F

    DFS to find every combinations of the string, if the substring is not Palindrome, ignore it then go to the next.

    public class Solution {
        List<List<String>> result = new ArrayList<List<String>>();
        public List<List<String>> partition(String s) {
            helper(s, new ArrayList<String>());
            return result;
        }        
        
        public void helper(String s, List<String> cur){                 //DFS every combinations
            if(s.length() == 0){result.add(cur); return;}        
            for(int i = 1; i <= s.length(); i++){
                String sub = s.substring(0,i);
                if(isPal(sub)){
                    List<String> newList = new ArrayList<String>(cur);
                    newList.add(sub);
                    helper(s.substring(i,s.length()), newList);
                }
                else continue;                                    //not palindrome, ignore it
            }        
        }                
        
        public boolean isPal(String str){
            int l = 0;
            int r = str.length()-1;
            while(l <= r){
                if(str.charAt(l) != str.charAt(r))  return false;
                l++;r--;
            }
            return true;
        }
    } 
    

    note: I found some people using the same method of mine, but they like to call their methods "backtracking", it is actually DFS, note backtracking.


  • 0
    Z

    Why do you use newList rather than just cur.add(sub) ?


  • 2
    B

    I felt sad that you don't know backtracking belongs to DFS...


Log in to reply
 

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