首页 > 代码库 > Problem Palindrome Partitioning

Problem Palindrome Partitioning

Problem Description:

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

Return all possible palindrome partitioning of s.

 

Solution:

 1     public List<List<String>> partition(String s) { 2 List<List<String>> l = new LinkedList<List<String>>(); 3         List<String> ll = new LinkedList<String>(); 4  5         if (s.length() == 1) { 6             ll.add(s); 7             l.add(ll); 8             return l; 9         }10         for (int i = 0; i < s.length(); i++)  {11             String str = s.substring(0, i+1);12             if (! isPalindrome(str)) {13                 continue;14             } else {15                 List<List<String>> others = partition(s.substring(i+1)); 16                 if (others.size() > 0) {17                     for (List<String> other : others) {18                         other.add(0, s.substring(0, i+1));19                         l.add(other);                    20                     }21                 } else {22                     ll.add(str);23                     l.add(ll);24                     return l;25                 }26                 27             }28         }29 30         return l;31     }32     public boolean isPalindrome(String s) {33         return s.equals(new StringBuilder(s).reverse().toString());34     }