CodeCollection2018
8/30/2019 - 12:44 PM

Palindrome Partitioning--分割成回文串

给定某个字符串，将其分割使得每个子串都是回文串。求所有的分割情况。 需要用DFS来解的题目，既然题目要求找到所有可能拆分成回文数的情况，那么肯定是所有的情况都要遍历到，对于每一个子字符串都要分别判断一次是不是回文数，那么肯定有一个判断回文数的子函数，还需要一个DFS函数用来递归，再加上原本的这个函数，总共需要三个函数来求解。我们将已经检测好的回文子串放到字符串数组out中，当s遍历完了之后，将out加入结果res中。那么在递归函数中我们必须要知道当前遍历到的位置，用变量start来表示，所以在递归函数中，如果start等于字符串s的长度，说明已经遍历完成，将out加入结果res中，并返回。否则就从start处开始遍历，由于不知道该如何切割，所以我们要遍历所有的切割情况，即一个字符，两个字符，三个字符，等等。。首先判断取出的子串是否是回文串，调用一个判定回文串的子函数即可，这个子函数传入了子串的起始和终止的范围，若子串是回文串，那么我们将其加入out，并且调用递归函数，此时start传入 i+1，之后还要恢复out的状态。

DFS
content_copyfile_download
//采用DFS来搜索，其实就是暴力搜索，非常类似于求数组元素的全排列问题，但是有一点不同。
public List<List<String>> partition(String s){
    List<List<String>> res = new ArrayList<>();
    List<String> temp = new ArrayList<>();
    partition_helper(s,0,temp,res);
    return res;
}
public void partition_helper(String s,int start,List<String> temp,List<List<String>> res){
    if(start==s.length()){
        List<String> t = new ArrayList<>();
        for(String item : temp) t.add(item);
        return;
    }
    for(int i = start; i < s.length(); i++){
        if(!isPalindrome(s,start,i)) continue;
        temp.add(s.substring(start,i+1));
        partition_helper(s,i+1,temp,res);
        temp.remove(temp.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;
}
dp-dfs
content_copyfile_download
//采用预先求DP数组，其中dp数组是二维数组，DP[i][j]代表字符串中从i到j是否是回文字符串。然后再按照上面的逻辑进行DFS从而提高效率，这样可以减少重复计算。
//又是用预数组减少重复计算。
public List<List<String>> partition(String s){
    int n = s.length();
    List<List<String>> res = new Arraylist<>();
    List<String> temp = new ArrayList<>();
    boolean[][] dp = new boolean[n][n];
    for(int i =0; i < n; i++){
        dp[i] = new boolean[n];
        for(int j = 0; j < i; j++){
            if(s.charAt(i)==s.charAt(j) && (i-j<=2 || dp[j+1][i-1]))
                dp[j][i] = true;
        }
    }
    partition_helper(s,0,dp,temp,res);
    return res;
}
public void partition_helper(String s,int start,boolean [][] dp,List<String> temp,List<List<String>> res){
    if(start==s.length()) {
        List<String> t = new ArrayList<String>();
        for(int i = start; i < s.length(); i++){
            if(!dp[start][i]) continue;
            temp.add(s.substring(start,i+1));
            partition_helper(s,i+1,temp,res);
            temp.remove(temp.size()-1);
        }
    }
}
dfs
content_copyfile_download
//还是DFS，但是每次递归形式变化，传参中不再有start/temp_List/res_list，而是只有字符串，所以返回值就是List<List<>>了。
public List<List<String>> partition(String s){
    List<List<String>> s = new ArrayList<>();
    if(s.isEmpty()) return s;
    for(int i = 0; i < s.length(); i++){
        if(!isPalindrome(s,i+1)) continue;
        for(List<String> list : partition(s.substring(i+1))){
            list.add(s.substring(0,i+1));
            res.add(list);
        }
    }
}
public boolean isPalindrome(String s,int n){
    for(int i = 0 ; i < n/2; i++)
        if(s.charAt(i)!=s.charAt(n-i-1)) return false;
    return true;
}