LeetCode [131] Palindrome Partitioning

 131. Palindrome Partitioning

Medium

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

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

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; } }