回溯---分割字符串使得每個部分都是回文數

分割字符串使得每個部分都是回文數

131. Palindrome Partitioning (Medium)

For example, given s = "aab",
Return[["aa","b"],["a","a","b"]
]

題目描述：

給定一個字符串，將其分割成回文串，并返回所有的分割結果。

思路分析：

求子串問題，也可以用到回溯思想，我們只需要判斷分割出來的字符串是否是回文，如果是回文就添加到結果中。

代碼：

public List<List<String>>partition(String s){List<List<String>>res=new ArrayList<>();List<String>list=new ArrayList<>();doPartition(s,res,list);return res;
}
public void doPartition(String s,List<List<String>>res,List<String>list){if(s.length()==0){res.add(new ArrayList<>(list));return;}for(int i=0;i<s.length();i++){if(isPalindrome(s,0,i)){ //判斷是否為回文list.add(s.substring(0,i+1));doPartition(s.substring(i+1),res,list);list.remove(list.size()-1);}}
}
public boolean isPalindrome(String s,int start,int end){while(start<end){if(s.charAt(start++)!=s.charAt(end--))return false;}return true;
}