LeetCode 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实现

回溯

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        if (s == null || s.length() == 0)
            return result;
        backtrace(result, s, new ArrayList<>());
        return result;
    }

    private void backtrace(List<List<String>> result, String s, ArrayList temp) {
        if (s.length() == 0) {//结束条件
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < s.length(); i++) {
            if (isPalindrome(s, 0, i)) {
                temp.add(s.substring(0, i + 1));//[0,i]
                backtrace(result, s.substring(i + 1), temp);//回溯[i+1,last] last指最后一个元素
                temp.remove(temp.size() - 1);
            }
        }
    }

    //判断回文序列
    private boolean isPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start++) != s.charAt(end--))
                return false;
        }
        return true;
    }
}