131. Palindrome Partitioning ⭐

Medium
Given a string s, partition s such that every
substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
Example 1:
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
Example 2:
Input: s = "a"
Output: [["a"]]
Constraints:
  • 1 <= s.length <= 16
  • s contains only lowercase English letters.

解題

func partition(s string) [][]string {
res := make([][]string, 0)
​
var dfs func(string, []string)
dfs = func(str string, cur []string) {
// 終止條件
if len(str) == 0 {
res = append(res, append([]string{}, cur...))
return
}
​
// backtracking
for i:=1; i<=len(str); i++ {
if isPalindrome(str[:i]) {
cur = append(cur, str[:i])
dfs(str[i:], cur)
cur = cur[:len(cur) - 1]
}
}
​
}
​
dfs(s, []string{})
​
return res
}
​
func isPalindrome(s string) bool {
if len(s) == 1 { return true }
​
left, right := 0, len(s) - 1
for left < right {
if s[left] != s[right] {
return false
}
left++
right--
}
​
return true
}