LeetCode-回文串分割

問題描述

給定一個字元串 s，将 s 分割成一些子串，使每個子串都是回文串。

傳回 s 所有可能的分割方案。

示例:

輸入: "aab"
輸出:
[
  ["aa","b"],
  ["a","a","b"]
]
           

直接看代碼

package solution;



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

class Solution2 {
    public static void main(String[] args) {
        new Solution2().partition("aab");
    }
    List results;
    public List<List<String>> partition(String s) {
        results = new ArrayList<ArrayList<String>>();
        boolean[] cut = new boolean[s.length()];
        find(s,0,cut);
        return results;
    }

    private void find(String s,int index,boolean[] cut){
        //一輪周遊完畢，開始分割
        if(index == s.length()){
            List<String> temp = new ArrayList<String>();
            int begin = 0,last = 0;
            while(last < s.length()){
                if(cut[last]){
                    temp.add(s.substring(begin,last+1));
                    begin = last+1;
                }
                last++;
            }
            results.add(temp);

        }
        //向右周遊回文字元串。
        for(int i=index;i<s.length();i++){
            //起點為index，i向後周遊，标記回文串
            if(isPalindrome(s,index,i)){
                cut[i] = true;
                //找到一個回文串，從i+1處開始找
                find(s,i+1,cut);
                //當一輪周遊完後将所有标記清除
                cut[i]=false;
            }
        }
    }


    //判斷是否為回文字元串
    private boolean isPalindrome(String s,int begin,int last){
        while(begin < last && s.charAt(begin) == s.charAt(last)){
            begin++;
            last--;
        }
        return begin >= last;
    }
}