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
}