palindrome-partitioning分割成回文串 go

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.
For example, given s ="aab",
Return
  [
    ["aa","b"],
    ["a","a","b"]
  ] 

思路：

• 一般找出所有解使用DFS，最优解用动态规划。
• 用递归解，用动规和回溯算法也能解。
• 树的含义。子节点为切一段子串的，所有切法。对于是回文串的继续递归子问题求解。
• “回文的判定”如同“节点是否遍历过的判定”。解为遍历到根节点（空串）的“路径”。
• 算法形如dfs，dfs算法复杂度和bfs相同，用邻接矩阵为O(n^2)，用邻接点数组O(e)。
• 对于go，切片是传值的。如果切片不加指针，res无法积累结果。
• collect可以用值拷贝，方便加入集合res。但最好用引用拷贝提高效率，再加入集合前使用前拷贝copy()复制。

细节：

• 切片是不定长数组，可以当链表集合保存结果，不必使用标准库链表。

• 会用二维切片初始化和二维数组初始化。对于用数组还是用切片的选取。

• 声明变量var name必须初始化赋值，var name string可以只声明。

• 用切片代替链表集合。切片直接初始化，或者直接赋指针，不需要make。作集合用时，可以直接赋指针，也可以选取部分元素slice[m:n]。一般不用copy前拷贝。

• go不允许将最终return放在最终if中。

• go不允许书写str[idx++] = sp的形式。

  //二维切片初始化。第二维make初始化指定了长度，所以可以用赋值，第一维没有make()，不能用x[i] = str。
  f := make([][]int, n)
  for i := 0; i < len(matrix); i++ {
  f[i] = make([]int, n)
  //注意思有类型推演符:
  }
  //第一次make变量未初始化，有推演符:，第2次变量make已初始化，无推演符。
  //二维数组声明var array [n][n]int。由于是值拷贝，不能传址。
  //二维数组初始化var array [2][2]int = [2][2]int{{0,1},{0,1}}

//二维切片作集合时，直接赋值，不make
//make切片必须指定长度，这个可以理解，ArrayList也是有初始大小的，go把权力交给了程序员以避免开销。
    var strings [][]string
    str := []string{"a", "b", "c"}
    strings[0] = str



//传值的切片，导致无法拷贝结果
func dfs(s string, collect *[]string, res [][]string) {
    if s == "" {
        //error code
        fmt.Println(collect)
        res = append(res, *collect)
        fmt.Print("res is")
        for _,elem := range res {
            fmt.Print(elem)
        }
        //到达叶节点，递归返回
        return
    }
}

所以，结果res是传址的，负责方法内外的沟通。collect要是传值的，由于collect通过调用append映射到res，传址的collect更新后，不仅新加入的collect值会变，原来已加入的Collect也会改变。简之，集合添加元素用值拷贝。

解（递归时，collect为值拷贝）：

//注释的代码用于测试
package main

import "fmt"

func partition(s string) [][]string {
    var res [][]string
    var collect []string
    dfs(s, collect, &res)
    return res
}

func dfs(s string, collect []string, res *[][]string) {
    if s == "" {
        //tip
        //fmt.Println(collect)
        *res = append(*res, collect)
        //fmt.Print("res is")
        //for _,elem := range *res {
        //  fmt.Print(elem)
        //}
        //到达叶节点，递归返回
        return
    }
    for i := 1; i <= len(s); i++ {
        child := s[0:i]
        if isPalindrome(child) {
            collect = append(collect, child)
            dfs(s[i:], collect, res)
            //递归完成剩余子树，要恢复状态
            //取指针优先于索引下标
            collect = (collect)[0 : len(collect)-1]
        }
    }

}

func isPalindrome(s string) bool {
    len := len(s)
    for i := 0; i < len/2; i++ {
        //字串可以直接[]，不需要避免charAt()
        if s[i] != s[len-1-i] {
            return false
        }
    }
    return true
}

func main() {
    str := "aab"
    res := partition(str)
    for _,elem := range res {
        fmt.Print(elem)
    }
}

解（在递归中collect引用传递）：

package main

import "fmt"

func partition(s string) [][]string {
    var res [][]string
    var collect []string
    dfs(s, &collect, &res)
    return res
}

func dfs(s string, collect *[]string, res *[][]string) {
    if s == "" {
        //error code
        collected := make([]string,len(*collect))
        copy(collected,*collect)
        *res = append(*res, collected)
        //到达叶节点，递归返回
        return
    }
    for i := 1; i <= len(s); i++ {
        child := s[0:i]
        if isPalindrome(child) {
            *collect = append(*collect, child)
            dfs(s[i:], collect, res)
            //递归完成剩余子树，要恢复状态
            //取指针优先于索引下标
            *collect = (*collect)[0 : len(*collect)-1]
        }
    }

}

func isPalindrome(s string) bool {
    len := len(s)
    for i := 0; i < len/2; i++ {
        //字串可以直接[]，不需要避免charAt()
        if s[i] != s[len-1-i] {
            return false
        }
    }
    return true
}

func main() {
    str := "aab"
    res := partition(str)
    for _,elem := range res {
        fmt.Print(elem)
    }
}