130. 被围绕的区域 Surrounded Regions

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例 1：

输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

示例 2：

输入：board = [["X"]]

输出：[["X"]]

提示：

m == board.length

n == board[i].length

1 <= m, n <= 200

board[i][j] 为 'X' 或 'O'

代码1： DFS

package main
import (
  "fmt"
)
func solve(board [][]byte) {
  if len(board) == 0 || len(board[0]) == 0 {
    return
  }
  m, n := len(board), len(board[0])
  // 从边界的'O'出发，将与其相连的'O'标记为'A'
  for i := 0; i < m; i++ {
    dfs(board, i, 0)
    dfs(board, i, n-1)
  }
  for j := 0; j < n; j++ {
    dfs(board, 0, j)
    dfs(board, m-1, j)
  }
  // 将未被标记的'O'填充为'X'，将标记为'A'的'O'恢复为'O'
  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if board[i][j] == 'O' {
        board[i][j] = 'X'
      } else if board[i][j] == 'A' {
        board[i][j] = 'O'
      }
    }
  }
}
func dfs(board [][]byte, i, j int) {
  if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) || board[i][j] != 'O' {
    return
  }
  board[i][j] = 'A'
  dfs(board, i-1, j)
  dfs(board, i+1, j)
  dfs(board, i, j-1)
  dfs(board, i, j+1)
}
func ArrayToString(arr []byte) string {
  res := "["
  for i := 0; i < len(arr); i++ {
    res += string(arr[i])
    if i != len(arr)-1 {
      res += ","
    }
  }
  return res + "]"
}
func main() {
  board := [][]byte{
    {'X', 'X', 'X', 'X'},
    {'X', 'O', 'O', 'X'},
    {'X', 'X', 'O', 'X'},
    {'X', 'O', 'X', 'X'}}
  solve(board)
  for _, row := range board {
    fmt.Println(ArrayToString(row))
  }
}

输出：

[X,X,X,X]

[X,O,X,X]

代码2： BFS

package main
import (
  "fmt"
)
func solve(board [][]byte) {
  if len(board) == 0 || len(board[0]) == 0 {
    return
  }
  m, n := len(board), len(board[0])
  // 从边界的'O'出发，将与其相连的'O'标记为'A'
  queue := make([][2]int, 0)
  for i := 0; i < m; i++ {
    if board[i][0] == 'O' {
      queue = append(queue, [2]int{i, 0})
    }
    if board[i][n-1] == 'O' {
      queue = append(queue, [2]int{i, n - 1})
    }
  }
  for j := 0; j < n; j++ {
    if board[0][j] == 'O' {
      queue = append(queue, [2]int{0, j})
    }
    if board[m-1][j] == 'O' {
      queue = append(queue, [2]int{m - 1, j})
    }
  }
  for len(queue) > 0 {
    i, j := queue[0][0], queue[0][1]
    queue = queue[1:]
    board[i][j] = 'A'
    if i > 0 && board[i-1][j] == 'O' {
      queue = append(queue, [2]int{i - 1, j})
    }
    if i < m-1 && board[i+1][j] == 'O' {
      queue = append(queue, [2]int{i + 1, j})
    }
    if j > 0 && board[i][j-1] == 'O' {
      queue = append(queue, [2]int{i, j - 1})
    }
    if j < n-1 && board[i][j+1] == 'O' {
      queue = append(queue, [2]int{i, j + 1})
    }
  }
  // 将未被标记的'O'填充为'X'，将标记为'A'的'O'恢复为'O'
  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if board[i][j] == 'O' {
        board[i][j] = 'X'
      } else if board[i][j] == 'A' {
        board[i][j] = 'O'
      }
    }
  }
}
func ArrayToString(arr []byte) string {
  res := "["
  for i := 0; i < len(arr); i++ {
    res += string(arr[i])
    if i != len(arr)-1 {
      res += ","
    }
  }
  return res + "]"
}
func main() {
  board := [][]byte{
    {'X', 'X', 'X', 'X'},
    {'X', 'O', 'O', 'X'},
    {'X', 'X', 'O', 'X'},
    {'X', 'O', 'X', 'X'}}
  solve(board)
  for _, row := range board {
    fmt.Println(ArrayToString(row))
  }
}

131. 分割回文串 Palindrome Partitioning

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

输入：s = "aab"

输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"

输出：[["a"]]

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

代码1： 动态规划

package main
import (
  "fmt"
  "strings"
)
func partition(s string) [][]string {
  n := len(s)
  dp := make([][]bool, n)
  for i := range dp {
    dp[i] = make([]bool, n)
  }
  for j := 0; j < n; j++ {
    for i := 0; i <= j; i++ {
      if s[i] == s[j] && (j-i <= 2 || dp[i+1][j-1]) {
        dp[i][j] = true
      }
    }
  }
  res := make([][]string, 0)
  path := make([]string, 0)
  dfs(s, 0, dp, path, &res)
  return res
}
func dfs(s string, start int, dp [][]bool, path []string, res *[][]string) {
  if start == len(s) {
    tmp := make([]string, len(path))
    copy(tmp, path)
    *res = append(*res, tmp)
    return
  }
  for i := start; i < len(s); i++ {
    if dp[start][i] {
      path = append(path, s[start:i+1])
      dfs(s, i+1, dp, path, res)
      path = path[:len(path)-1]
    }
  }
}
func ArrayToString(arr []string) string {
  res := "["
  for i := 0; i < len(arr); i++ {
    res += arr[i]
    if i != len(arr)-1 {
      res += ","
    }
  }
  return res + "]"
}
func main() {
  str := "aab"
  fmt.Println(strings.Join(strings.Fields(fmt.Sprint(partition(str))), ","))
  str = "a"
  fmt.Println(strings.Join(strings.Fields(fmt.Sprint(partition(str))), ","))
}

输出：

[[a,a,b],[aa,b]]

[[a]]

代码2： 回溯

package main
import (
  "fmt"
  "strings"
)
func partition(s string) [][]string {
  res := make([][]string, 0)
  path := make([]string, 0)
  backtrack(s, 0, path, &res)
  return res
}
func backtrack(s string, start int, path []string, res *[][]string) {
  if start == len(s) {
    tmp := make([]string, len(path))
    copy(tmp, path)
    *res = append(*res, tmp)
    return
  }
  for i := start; i < len(s); i++ {
    if isPalindrome(s, start, i) {
      path = append(path, s[start:i+1])
      backtrack(s, i+1, path, res)
      path = path[:len(path)-1]
    }
  }
}
func isPalindrome(s string, start, end int) bool {
  for start < end {
    if s[start] != s[end] {
      return false
    }
    start++
    end--
  }
  return true
}
func ArrayToString(arr []string) string {
  res := "["
  for i := 0; i < len(arr); i++ {
    res += arr[i]
    if i != len(arr)-1 {
      res += ","
    }
  }
  return res + "]"
}
func main() {
  str := "aab"
  fmt.Println(strings.Join(strings.Fields(fmt.Sprint(partition(str))), ","))
  str = "a"
  fmt.Println(strings.Join(strings.Fields(fmt.Sprint(partition(str))), ","))
}

132. 分割回文串 II Palindrome Partitioning II

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的 最少分割次数 。

示例 1：

输入：s = "aab"

输出：1

解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2：

输入：s = "a"

输出：0

示例 3：

输入：s = "ab"

输出：1

提示：

1 <= s.length <= 2000

s 仅由小写英文字母组成

代码1：动态规划

package main
import (
  "fmt"
)
func minCut(s string) int {
  n := len(s)
  dp := make([][]bool, n)
  for i := range dp {
    dp[i] = make([]bool, n)
  }
  for j := 0; j < n; j++ {
    for i := 0; i <= j; i++ {
      if s[i] == s[j] && (j-i <= 2 || dp[i+1][j-1]) {
        dp[i][j] = true
      }
    }
  }
  cut := make([]int, n)
  for i := 0; i < n; i++ {
    if dp[0][i] {
      cut[i] = 0
      continue
    }
    cut[i] = i
    for j := 0; j < i; j++ {
      if dp[j+1][i] {
        cut[i] = min(cut[i], cut[j]+1)
      }
    }
  }
  return cut[n-1]
}
func min(a, b int) int {
  if a < b {
    return a
  }
  return b
}
func main() {
  str := "aab"
  fmt.Println(minCut(str))
  str = "a"
  fmt.Println(minCut(str))
  str = "ab"
  fmt.Println(minCut(str))
}

输出：

代码2： 动态规划

package main
import (
  "fmt"
)
func minCut(s string) int {
  n := len(s)
  cut := make([]int, n)
  for i := range cut {
    cut[i] = i
  }
  for i := 0; i < n; i++ {
    expand(s, i, i, &cut)
    expand(s, i, i+1, &cut)
  }
  return cut[n-1]
}
func expand(s string, left, right int, cut *[]int) {
  for left >= 0 && right < len(s) && s[left] == s[right] {
    if left == 0 {
      (*cut)[right] = 0
    } else {
      (*cut)[right] = min((*cut)[right], (*cut)[left-1]+1)
    }
    left--
    right++
  }
}
func min(a, b int) int {
  if a < b {
    return a
  }
  return b
}
func main() {
  str := "aab"
  fmt.Println(minCut(str))
  str = "a"
  fmt.Println(minCut(str))
  str = "ab"
  fmt.Println(minCut(str))
}