leetcode-go/leetcode/medium/332.reconstruct-itinerary.go

type StringSlice []string

func (ss StringSlice) Len() int           { return len(ss) }
func (ss StringSlice) Less(i, j int) bool { return ss[i] < ss[j] }
func (ss StringSlice) Swap(i, j int)      { ss[i], ss[j] = ss[j], ss[i] }

func (ss *StringSlice) Push(x interface{}) {
	*ss = append(*ss, x.(string))
}

func (ss *StringSlice) Pop() interface{} {
	old := *ss
	n := len(old)
	x := old[n-1]
	*ss = old[0 : n-1]
	return x
}

func findItinerary(tickets [][]string) (res []string) {
	m := make(map[string]StringSlice)
	for i := 0; i < len(tickets); i++ {
		ss := m[tickets[i][0]]
		heap.Push(&ss, tickets[i][1])
		m[tickets[i][0]] = ss
	}
	dfs(&m, "JFK", &res)
	for l, r := 0, len(tickets); l < r; l, r = l+1, r-1 {
		res[l], res[r] = res[r], res[l]
	}
	return res
}

func dfs(m *map[string]StringSlice, dst string, res *[]string) {
	for (*m)[dst].Len() != 0 {
		ss := (*m)[dst]
		next := heap.Pop(&ss).(string)
		(*m)[dst] = ss
		dfs(m, next, res)
	}
	*res = append(*res, dst)
}