Palindrome Partitioning 分割字符串为回文@LeetCode

DFS回溯又一经典应用

package Level4;
import java.util.ArrayList;
import java.util.Hashtable;
/**
*
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"]
]
*
*/
public class S136 {
public static void main(String[] args) {
String s = "aab";
System.out.println(partition(s));
}
public static ArrayList<ArrayList<String>> partition(String s) {
ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>();
ArrayList<String> al = new ArrayList<String>();
Hashtable<String, Boolean> ht = new Hashtable<String, Boolean>();
dfs(s, 0, ht, ret, al);
return ret;
}
public static void dfs(String s, int start, Hashtable<String, Boolean> ht, ArrayList<ArrayList<String>> ret, ArrayList<String> al){
if(start == s.length()){
// 返回条件
ret.add(new ArrayList<String>(al));
return;
}
for(int i=start; i<s.length(); i++){
// 拓展状态
boolean isPalindrome = false;
String substr = s.substring(start, i+1);
// 子字符串
if(ht.get(substr) != null){
// 先尝试在hashtable中查找，避免重复查找
isPalindrome = ht.get(substr);
}else{
// 判断是否palindrome，放入ht
isPalindrome = checkPalindrome(substr);
ht.put(substr, isPalindrome);
}
if(isPalindrome){
al.add(substr);
// 执行拓展动作
dfs(s, i+1, ht, ret, al);
al.remove(al.size()-1);	// 撤销动作
}
}
}
public static boolean checkPalindrome(String s){
if(s.length() == 0){
return true;
}
for(int i=0; i<=s.length()/2; i++){
if(s.charAt(i) != s.charAt(s.length()-1-i)){
return false;
}
}
return true;
}
}

不用Hashtable也可以通过

public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> ret = new ArrayList<List<String>>();
rec(ret, new ArrayList<String>(), s, 0);
return ret;
}
public void rec(List<List<String>> ret, List<String> list, String s, int pos) {
if(pos == s.length()) {
ret.add(new ArrayList<String>(list));
return;
}
for(int i=pos; i<s.length(); i++) {
String substr = s.substring(pos, i+1);
if(isPalindrome(substr)) {
list.add(substr);
rec(ret, list, s, i+1);
list.remove(list.size()-1);
}
}
}
public boolean isPalindrome(String s) {
int left = 0, right = s.length()-1;
while(left <= right) {
if(s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
}

最后

以上就是靓丽小蚂蚁为你收集整理的Palindrome Partitioning 分割字符串为回文@LeetCode的全部内容，希望文章能够帮你解决Palindrome Partitioning 分割字符串为回文@LeetCode所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。