[LintCode] Palindrome Partitioning

java 4 2016-02-29 13:03
女装

Problem

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example

Given s = "aab", return:

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

Note

把dfs方法多写几遍就好了,别的地方没有难度。

Solution

public class Solution {

public List<List<String>> partition(String s) {
    // write your code here
    List<List<String>> res = new ArrayList<List<String>>();
    List<String> tem = new ArrayList<String>();
    if (s.length() == 0 || s == null){
        return res;
    }
    dfs(res, tem, s, 0);
    return res;
}
public void dfs(List<List<String>> res, List<String> tem, String s, int start){
    if (start == s.length()){
        res.add(new ArrayList<String>(tem));
        return;
    }
    for (int i = start; i < s.length(); i++){
        String str = s.substring(start, i + 1);
        if (isPalindrome(str)){
            tem.add(str);
            dfs(res, tem, s, i + 1); //start+=1
            tem.remove(tem.size() - 1);
        }
    }
}
public boolean isPalindrome(String str){
    int l = 0;
    int r = str.length()-1;
    while (l < r){
        if (str.charAt(l) != str.charAt(r)) return false;
        l++;
        r--;
    }
    return true;
}

}

女装
文章评论