[leetcode] wordsearch

前端之家收集整理的这篇文章主要介绍了[leetcode] wordsearch前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

problem: https://oj.leetcode.com/problems/word-search/
代码https://play.golang.org/p/d5wP691Pbg

  1. package main
  2.  
  3. import (
  4. "fmt"
  5. )
  6.  
  7. func main() {
  8. arr := [][]byte{
  9. {'A','B','C','E'},{'S','F','S'},{'A','D','E',}
  10. //word := []byte("ABCESC")
  11. word := []byte("SFCE")
  12. arrI,arrJ,ok := FindFirstCharPositions(arr,word[0])
  13. if ok {
  14. fmt.Printf("%d,%d\n",arrI,arrJ)
  15. }
  16. fmt.Println(DFSTraverse(arr,word,arrJ))
  17. }
  18.  
  19. func DFSTraverse(arr [][]byte,word []byte,arrI []int,arrJ []int) (ret bool) {
  20. //初始化visited函数
  21. lenArr := len(arr)
  22. visited := make([][]bool,lenArr)
  23. for i := 0; i < lenArr; i++ {
  24. visited[i] = make([]bool,len(arr[i]))
  25. }
  26. lenArrI := len(arrI)
  27. //lenArrJ := len(arrJ)
  28. for i := 0; i < lenArrI; i++ {
  29. //fmt.Println(i)
  30. ret = DFS(arr,visited,arrI[i],arrJ[i])
  31. if ret == true {
  32. return true
  33. }
  34. }
  35. return
  36. }
  37.  
  38. //dfs traverse,when found return true
  39. func DFS(arr [][]byte,index int,visited [][]bool,i int,j int) (ret bool) {
  40. if i < 0 || j < 0 || i >= len(visited) || j >= len(visited[i]) || visited[i][j] {
  41. return false
  42. }
  43. if index == len(word) {
  44. return true
  45. }
  46. if arr[i][j] != word[index] {
  47. return false
  48. }
  49.  
  50. fmt.Printf("%c:%d,%d ",word[index],i,j)
  51. visited[i][j] = true //标识为已访问
  52. index++
  53. //fmt.Println("yes")
  54. ret = DFS(arr,index,i-1,j) ||
  55. DFS(arr,j+1) ||
  56. DFS(arr,i+1,j-1)
  57. visited[i][j] = false
  58. return ret
  59. }
  60.  
  61. func FindFirstCharPositions(arr [][]byte,c byte) (arrI []int,arrJ []int,ok bool) {
  62. lenArrRow := len(arr)
  63. if lenArrRow == 0 {
  64. return
  65. }
  66. lenArrCol := len(arr[0])
  67.  
  68. for i := 0; i < lenArrRow; i++ {
  69. for j := 0; j < lenArrCol; j++ {
  70. if arr[i][j] == c {
  71. arrI = append(arrI,i)
  72. arrJ = append(arrJ,j)
  73. ok = true
  74. }
  75. }
  76. }
  77. return
  78. }

猜你在找的Go相关文章