1、分割回文串——回溯法

题目：

给定一个字符串s，将s分割成一些子串，使每个子串都是回文串。

返回s所有可能的回文串分割方案。

样例

给出 s = "aab"，返回

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

标签 Expand 

回溯法  深度优先搜索

 

package unit1;

import java.util.ArrayList;
import java.util.List;

public class Huiwen {
    
    /**检查是否为回文
     * @param s
     * @return
     */
    public static boolean check(String s){
        String s1="";
        char[] c=s.toCharArray();
        /*Character[] ctr=new Character[s.length()];    
        byte[] b=s.getBytes();*/
        for(int i=s.length()-1;i >=0;i--){
            /*System.out.println(b[i]);*/
            c[i]=s.charAt(i);
//            System.out.println(c[i]);
            s1=s1+c[i];
//            System.out.println(s1);
        }
        if(s1.equals(s)){
            return true;
        }
        else{
            return false;
        }
                  
    }
    
    /**获取所有不为空的回文子串
     * @param str
     */
    public static void partion(String str){
        String substr="";
        for(int i=0;i<str.length();i++){
            for (int j=i;j<str.length()+1;j++){//注意这里j的取值范围，因为截取函数substring(i,j)包含i不包含j
                substr=str.substring(i, j);                
                if(!("".equals(substr))&&check(substr)){//打印所有不为空的回文子串
                    System.out.println("i:"+i+"j:"+j+"substr:"+substr);
                }
                
            }
        }
        
    }
    
    /**获取字符串S的回文分割法集合
     * @param s
     * @return
     */
    public static ArrayList<ArrayList<String>> partition(String s) {
        // write your code here
        ArrayList<ArrayList<String>> pLists = new ArrayList<ArrayList<String>>();
          int length = s.length();
          ArrayList<String> array = new ArrayList<String>();
          if (s.length() == 0 || s == null) {
               pLists.add(array);
               return pLists;
          }

          helper(s, pLists, array, 0);
          return pLists;
    }
   
    public  static void helper(String s, ArrayList<ArrayList<String>> pLists,
            ArrayList<String> array, int start) {
          if (start == s.length()) {
               pLists.add(array);
               return;
          }
          for (int i = start; i < s.length(); i++) {
               if (check(s.substring(start, i + 1))) {
                   ArrayList<String> tmp = new ArrayList<String>(array);
                    tmp.add(s.substring(start, i + 1));
                    helper(s, pLists, tmp, i + 1);
               }
          }

     }
    public static void main(String[] args){
        int flag=2;
        if (flag==1){//获取全部的不为空的回文子字符串
            partion("aab");
        }
        else if (flag==2){//获取S的回文分割方案
            System.out.println(partition("aab"));
        }
        
        
    }
  
}