题目链接：131

思路

对于要求 “求出所有可能”的题目，dfs 是必不可少的，这道题也是一样。

本题的关键点在于如何减少dfs过程中对 字符串是否为回文串 的重复判断。使用 dp 可以将字符串的每一个子区间是否是回文串记录下来，从而减少重复判断。但是对于本题来说，并不是每一个子区间都会被判断到，因此只需要在正常判断后加一个buffer记录就可以了，没必要专门使用dp进行预处理。

// string = palindrome part + unpalindrome part
var ans [][]string
var prefix []string
var palindromeBuffer map[string]bool

func partition(s string) [][]string {
    ans = make([][]string, 0)
    prefix = make([]string, 0)
    palindromeBuffer = make(map[string]bool)
    dfs(s)
    return ans
}

func dfs(s string) {
    // base case
    if len(s) < 1 {
        prefixCp := make([]string, len(prefix))
        copy(prefixCp, prefix)
        ans = append(ans, prefixCp)
        return
    }
    for i := 1; i <= len(s); i++ {
        if isPalindrome(s[:i]) {
            prefix = append(prefix, s[:i])
            dfs(s[i:])
            prefix = prefix[:len(prefix)-1]
        }
    }
}

func isPalindrome(s string) bool {
    val, ok := palindromeBuffer[s]
    if ok {
        return val
    }
    for i := 0; i < len(s); i++ {
        if s[i] != s[len(s)-1-i] {
            palindromeBuffer[s] = false
            return false
        }
    }
    palindromeBuffer[s] = true
    return true
}

时间复杂度：O(n * 2ⁿ)，其中 n 是字符串 s 的长度。在最坏情况下，s 包含 n 个完全相同的字符。长度为 n 的字符串的划分方案数为 2^n-1，每一种划分方法需要 O(n) 的时间求出内部所有小块是否为回文串，因此总时间复杂度为 O(2ⁿ)。

空间复杂度：O(n * 2ⁿ)