131. Palindrome Partitioning #
题目 #
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Example:
Input: "aab"
Output:
[
["aa","b"],
["a","a","b"]
]
题目大意 #
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。
解题思路 #
- 要求输出一个字符串可以被拆成回文串的所有解，DFS 递归求解即可。
代码 #
package leetcode
// 解法一
func partition131(s string) [][]string {
if s == "" {
return [][]string{}
}
res, pal := [][]string{}, []string{}
findPalindrome(s, 0, "", true, pal, &res)
return res
}
func findPalindrome(str string, index int, s string, isPal bool, pal []string, res *[][]string) {
if index == len(str) {
if isPal {
tmp := make([]string, len(pal))
copy(tmp, pal)
*res = append(*res, tmp)
}
return
}
if index == 0 {
s = string(str[index])
pal = append(pal, s)
findPalindrome(str, index+1, s, isPal && isPalindrome131(s), pal, res)
} else {
temp := pal[len(pal)-1]
s = pal[len(pal)-1] + string(str[index])
pal[len(pal)-1] = s
findPalindrome(str, index+1, s, isPalindrome131(s), pal, res)
pal[len(pal)-1] = temp
if isPalindrome131(temp) {
pal = append(pal, string(str[index]))
findPalindrome(str, index+1, temp, isPal && isPalindrome131(temp), pal, res)
pal = pal[:len(pal)-1]
}
}
return
}
func isPalindrome131(s string) bool {
slen := len(s)
for i, j := 0, slen-1; i < j; i, j = i+1, j-1 {
if s[i] != s[j] {
return false
}
}
return true
}
// 解法二
func partition131_1(s string) [][]string {
result := [][]string{}
size := len(s)
if size == 0 {
return result
}
current := make([]string, 0, size)
dfs131(s, 0, current, &result)
return result
}
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)
}
}
}
func isPal(str string, s, e int) bool {
for s < e {
if str[s] != str[e] {
return false
}
s++
e--
}
return true
}