Friday, January 31, 2014

Palindrome Partitioning (Java)

LeetCode

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"]
  ]


Solution: DFS, Recursion

declare start point st, make it move from 0-> s.length(), for each st, check every substring generated by st and i, st+1<=i<=s.length(), if the substring is a palindrome then put it into ArrayList<String>  partition, if st reach s.length() mean we got a valid partition for given string s, then put it into ArrayList<ArrayList<String>> result;