lintcode：Palindrome Partitioning 分割回文串

题目：

分割回文串

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

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

样例

给出 s = "aab"，返回

  [

    ["aa","b"],

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

  ]

解题：

这个题目不好搞啊，需要动态规划

在这里，没有根据动态规划，也解决了，貌似是暴力解决

从下标pos开始，找到下标i使得 pos到i内是回文字符串，再从i+1开始，找到下一个回文串，这样一直找下去。。。

时间复杂度O(n²)

Java程序：

public class Solution {
    /**
     * @param s: A string
     * @return: A list of lists of string
     */
    public ArrayList<ArrayList<String>> partition(String s) {
        // write your code here
        ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
        if(s==null)
            return result;
        ArrayList<String> path = new ArrayList<String>();
        helper(s,path,0,result);
        return result;
    }
    private boolean isPalindrome(String s){
        int beg = 0;
        int end = s.length() - 1;
        while(beg<end){
            if(s.charAt(beg)!=s.charAt(end))
                return false;
            beg++;
            end--;
        }
        return true;
    }
    private void helper(String s,ArrayList<String> path,int pos,ArrayList<ArrayList<String>> result){
        if(pos==s.length()){
            result.add(new ArrayList<String>(path));
            return;
        }
        for(int i=pos+1;i<=s.length();i++){
            String prefix = s.substring(pos,i);
            if(!isPalindrome(prefix))
                continue;
            path.add(prefix);
            helper(s,path,i,result);
            path.remove(path.size()-1);
        }
    }
}

总耗时: 2017 ms

上面程序利用到的是深度优先遍历

DFS

(1) 判断是否结束

（2） for 循环取所有的子串

 2.1 判断是否是回文字符串

2.2 是加入，递归进行

2.3 不是，for循环下一位