this repo has no description
tulkdan.dev
1package main
2
3import (
4 "fmt"
5 "sort"
6)
7
8func permute(nums []int) [][]int {
9 permutations := [][]int{}
10
11 var backtrack func([]int, []bool)
12 backtrack = func (curr []int, pick []bool) {
13 if len(curr) == len(nums) {
14 permutations = append(permutations, append([]int{}, curr...))
15 return
16 }
17
18 for j, val := range nums {
19 if pick[j] {
20 continue
21 }
22
23 pick[j] = true
24 backtrack(append(curr, val), pick)
25 pick[j] = false
26 }
27 }
28
29 backtrack([]int{}, make([]bool, len(nums)))
30
31 return permutations
32}
33
34
35func subsetWithDup(nums []int) [][]int {
36 sort.Ints(nums)
37 result := [][]int{}
38
39 var backtrack func([]int, int)
40 backtrack = func(curr []int, i int) {
41 result = append(result, append([]int{}, curr...))
42
43 for j := i; j < len(nums); j++ {
44 if j > i && nums[j] == nums[j - 1] {
45 continue
46 }
47 backtrack(append(curr, nums[j]), j+1)
48 }
49 }
50
51 backtrack([]int{}, 0)
52
53 return result
54}
55
56
57func main() {
58 /**
59 a := exist([][]byte{
60 {'A', 'B', 'C', 'D'},
61 {'S', 'A', 'A', 'T'},
62 {'A', 'C', 'A', 'E'},
63 }, "CAT")
64 fmt.Println(a)
65
66 a = exist([][]byte{
67 {'A', 'B', 'C', 'D'},
68 {'S', 'A', 'A', 'T'},
69 {'A', 'C', 'A', 'E'},
70 }, "BAT")
71 fmt.Println(a)
72
73 */
74 board := [][]byte{
75 {'A', 'B', 'C', 'E'},
76 {'S', 'F', 'C', 'S'},
77 {'A', 'D', 'E', 'E'},
78 }
79 fmt.Println(exist(board, "ABCB"))
80 fmt.Println(exist(board, "SEE"))
81 fmt.Println(exist(board, "ABCCED"))
82 fmt.Println(exist([][]byte{{'A'}}, "A"))
83}
84
85func exist(board [][]byte, word string) bool {
86 hasSeen := make([][]bool, len(board))
87 for i, _ := range hasSeen {
88 hasSeen[i] = make([]bool, len(board[0]))
89 }
90
91 var backtracking func(int, int, int) bool
92 backtracking = func(x, y, l int) bool {
93 if l == len(word) {
94 return true
95 }
96 fmt.Printf("letter %q at X->%d Y->%d\n", word[l], x, y)
97
98 if x < 0 || y < 0 ||
99 x >= len(board[0]) || y >= len(board) ||
100 board[y][x] != word[l] || hasSeen[y][x] {
101 return false
102 }
103
104 fmt.Printf("Found letter %q at X -> %d Y -> %d\n", word[l], x, y)
105 hasSeen[y][x] = true
106 res := backtracking(x+1, y, l+1) ||
107 backtracking(x, y+1, l+1) ||
108 backtracking(x-1, y, l+1) ||
109 backtracking(x, y-1, l+1)
110 hasSeen[y][x] = false
111
112 return res
113 }
114
115 for y := 0; y < len(board); y++ {
116 for x := 0; x < len(board[0]); x++ {
117 if backtracking(x, y, 0) {
118 return true
119 }
120 }
121 }
122 return false
123}