005.重新安排行程

• 332.重新安排行程
  • 正常回溯（已经是最好的剪枝，但仍然超时）
  • 确定输入数据能有正确返回值

正常回溯

var (
	size int
	res []string
	helper map[string][]string
)
 
func findItinerary(tickets [][]string) []string {
	size = len(tickets)
	if size == 0 {
		return nil
	}
	res = make([]string, 0, size + 1)
	helper = map[string][]string{}
	for _, v := range tickets {
		helper[v[0]] = append(helper[v[0]], v[1])
	}
	for _, v := range helper {
		sort.Strings(v)
	}
 
	if backtracking("JFK") {
		return res
	}
	return nil
}
 
func backtracking(start string) bool {
	res = append(res, start)
	if len(res) == size + 1 {
		return true
	}
 
	for i, to := range helper[start] {
		if to == "" {
			continue
		}
		helper[start][i] = ""
		if backtracking(to) {
			return true
		}
		helper[start][i] = to
		res = res[:len(res) - 1]
	}
	return false
}

确定输入数据能有正确返回值

var (
	helper map[string][]string
	res []string
)
 
func findItinerary(tickets [][]string) []string {
	helper = map[string][]string{}
	for _, v := range tickets {
		helper[v[0]] = append(helper[v[0]], v[1])
	}
	for _, v := range helper {
		sort.Strings(v)
	}
 
	res = []string{}
	backtracking("JFK")
	return res
}
 
func backtracking(start string) {
	for len(helper[start]) > 0 {
		to := helper[start][0]
		helper[start] = helper[start][1:]
		backtracking(to)
	}
	res = append([]string{ start }, res...)
}