forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
0332-reconstruct-itenerary.go
48 lines (33 loc) · 887 Bytes
/
0332-reconstruct-itenerary.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
func findItinerary(tickets [][]string) []string {
adjMap := make(map[string][]string)
for i := 0; i < len(tickets); i++ {
adjMap[tickets[i][0]] = append(adjMap[tickets[i][0]], tickets[i][1])
}
for i := 0; i < len(tickets); i++ {
sort.Strings(adjMap[tickets[i][0]])
}
res := []string{"JFK"}
var dfs func(source string) bool
dfs = func(src string) bool {
if len(res) == len(tickets)+1 {
return true
}
if _, ok := adjMap[src]; !ok {
return false
}
destinationList := adjMap[src]
for i, destination := range destinationList {
adjMap[src] = append(adjMap[src][:i], adjMap[src][i+1:]...)
res = append(res, destination)
if dfs(destination) == true {
return true
}
adjMap[src] = append(adjMap[src][:i+1], adjMap[src][i:]...)
adjMap[src][i] = destination
res = res[:len(res)-1]
}
return false
}
dfs("JFK")
return res
}