Concise Java solution

  • 7

    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);
                    List<String> newList = new ArrayList<String>(cur);
                    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;
            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

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

  • 2

    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.