0131. Palindrome Partitioning | LeetCode Cookbook

[halfrost]

https://books.halfrost.com/leetcode/ChapterFour/0100~0199/0131.Palindrome-Partitioning/

[hanlins]

对于子串是不是回文可以用DP来加速。DP遍历子串的方式感觉面试不一定能想对或者解释清楚，于是可以用记忆化搜索。最后用DFS来收集结果。

const (
    NotEvaluated = iota
    IsPalindrome
    NotPalindrome
)

func partition(s string) (res [][]string) {
    dp := make([][]int8, len(s))
    for i := range dp {
        dp[i] = make([]int8, len(s) + 1)
    }
    
    var isPalindrome func(i, j int) (res bool)
    isPalindrome = func(i, j int) (res bool) {
        if i == j || i == j + 1 { return true }
        if dp[i][j] != NotEvaluated { return dp[i][j] == IsPalindrome }
        defer func() {
            if res {
                dp[i][j] = IsPalindrome
            } else {
                dp[i][j] = NotPalindrome
            }
        }()
        
        if s[i] != s[j-1] { return false }
        return isPalindrome(i+1, j-1)
    }
    
    var dfs func(i int, prev []string)
    dfs = func(i int, prev []string) {
        if i == len(s) {
            res = append(res, append([]string{}, prev...))
        }
        prev = append(prev, "")
        for j := i + 1; j <= len(s); j++ {
            if !isPalindrome(i, j) {
                continue
            }
            prev[len(prev)-1] = s[i:j]
            dfs(j, prev)
        }
    }
    
    dfs(0, nil)
    return
}

[wagaru]

想確認一下，這邊會需要透過 copy(temp, cur) 是因為 append(cur, s[start:i+1]) 回傳的位址可能跟 cur 相同嗎？

func dfs131(s string, idx int, cur []string, result *[][]string) {
	start, end := idx, len(s)
	if start == end {
		temp := make([]string, len(cur))
		copy(temp, cur)
		*result = append(*result, temp)
		return
	}
	for i := start; i < end; i++ {
		if isPal(s, start, i) {
			dfs131(s, i+1, append(cur, s[start:i+1]), result)
		}
	}
}