palindrome - 131. Palindrome Partitioning

131. Palindrome Partitioning

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

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
["aa","b"],
["a","a","b"]
]

思路：

题目意思是找出字符串中子串是回文字符串的所有组合，使用回溯来做。

代码：

java：

public class Solution {

    List<List<String>> resultLst;
    ArrayList<String> currLst;

    public List<List<String>> partition(String s) {
        resultLst = new ArrayList<List<String>>();
        currLst = new ArrayList<String>();
        backTrack(s,0);
        return resultLst;
    }

    public void backTrack(String s, int l){
        if(currLst.size() > 0 && l >= s.length()) {
                List<String> r = (ArrayList<String>) currLst.clone();
                resultLst.add(r);
        }
        for( int i = l; i < s.length(); i++) {
            if (isPalindrome(s,l,i)) {
                if (l == i)
                    currLst.add(Character.toString(s.charAt(i)));
                else
                    currLst.add(s.substring(l, i + 1));

                backTrack(s, i + 1);
                currLst.remove(currLst.size()-1);
            }
        }
    }

    public boolean isPalindrome(String str, int l, int r){
        if(l == r) return true;
        while(l < r){
            if(str.charAt(l) != str.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }
}