Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",

Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

Since we need to find all possible palindrome partitioning, we will use recursive dfs + backtrack to get all results.

The main idea is to split s into two parts: s1 = s.substring(0,i), s2 = s.substring(i). If s1 is a palindrome string, recursively check s2.

public List<List<String>> partition(String s) {
        List<List<String>> results = new ArrayList<List<String>>();
        if (s==null||s.isEmpty()) {
            return results;
        }

        partition(s, results, new ArrayList<String>());
        return results;
    }

    public void partition(String s, List<List<String>> results, List<String> result) {
        if (s.isEmpty()) {
            results.add(new ArrayList<String>(result));
            return;
        }

        for (int i=1; i<=s.length(); i++) {
            String str = s.substring(0,i);
            if (isPalindrome(str)) {
                result.add(str);
                partition(s.substring(i), results, result);
                result.remove(result.size()-1);
            }
        }      
    }


    public boolean isPalindrome(String s) {
        int i=0;
        int j=s.length()-1;
        while (i<=j) {
            if(s.charAt(i)!=s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }

        return true;
    }