[LeetCode] 131. Palindrome Partitioning

轉自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>
這題原本想用 DP 的方式來解

但因為答案需要所有的字串組合，所以最後還是使用 DFS 來找所有的組合

想法如下

• 檢查當下的 partition 是否可以形成一個 palindrome，如果可以，就先放到 vector裡面

• 使用 DFS 的概念，繼續往下找，當已經處理到最後一個字元，就放到 ans 裡面

code 如下(參考資料)