LeetCode-131

题目

结果

代码

思路挺简单的：枚举出所有可能的分割方法，然后逐一判断是否构成回文，难点在于如何枚举。

func partition(s string) [][]string {
   paths := make([][]string, 0)
   for _, ch := range s {
      // 1st element
      if len(paths) == 0 {
         paths = append(paths, []string{string(ch)})
         continue
      }

      // do not modify array when iterating
      toAppend := make([][]string, 0)
      for _, row := range paths {
         tmp := _copy(row)
         toAppend = append(toAppend, copyAndAppend(tmp, string(ch)))
         row[len(row)-1] += string(ch)
      }
      for _, v := range toAppend {
         paths = append(paths, v)
      }
   }

   ans := make([][]string, 0)
   // filter
   for _, v := range paths {
      if isPalindromes(v) {
         ans = append(ans, v)
      }
   }
   return ans
}

func isPalindromes(ss []string) bool {
   for _, v := range ss {
      if !isPalindrome(v) {
         return false
      }
   }
   return true
}

// is a palindrome
func isPalindrome(s string) bool {
   for i, j := 0, len(s)-1; i < j; {
      if s[i] != s[j] {
         return false
      }
      i++
      j--
   }
   return true
}

func copyAndAppend(ss []string, s string) []string {
   ans := make([]string, 0, len(ss)+1)
   for _, v := range ss {
      ans = append(ans, v)
   }
   ans = append(ans, s)
   return ans
}

func _copy(ss []string) []string {
   ans := make([]string, 0, len(ss))
   for _, v := range ss {
      ans = append(ans, v)
   }
   return ans
}

复杂度

有点算不明白，应该复杂度很高