leetcode palindrome-partitioning（Java）
Leetcode Palindrome Partitioning
package com.leetcode.str import java.util.ArrayList /** * Topic: * palindrome-partitioning * * Description of the topic: * Given a string s, partition s such that * every substring of the partition is a palindrome. * Return all possible palindrome partitioning of s. * For example, given s ='aab', * Return [ ['aa','b'], ['a','a','b'] ] * */ public class PalindromePartition { public ArrayList partition(String s) { if(s == null) { return null } ArrayList caches = new ArrayList() ArrayList cache = new ArrayList() partition(s,cache,caches) return caches } public void partition(String s, ArrayList cache, ArrayList caches) { if (s == null || s.isEmpty()) { caches.add(new ArrayList(cache)) return } int len = s.length() for (int i=1 i<=len i++) { String sub = s.substring(0,i) // The number of palindromes in front if (isPalindrome(sub)) { cache.add(sub) / / Process the following string partition(s.substring(i, len), cache, caches) / / Restore the list, delete the last element of the list cache.remove(cache.size() - 1) } } } private boolean isPalindrome(String str) { return new StringBuilder(str).reverse().toString().equals(str) } public static void main(String[] args) { String s = 'aab' ArrayList caches = new PalindromePartition().partition(s) for (ArrayList lst: caches) { System.out.println(lst) } } }