leetcode Reconstruct Itinerary

leetcode Reconstruct Itinerary

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets may form at least one valid itinerary.

Example 1: tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] Return ["JFK", "MUC", "LHR", "SFO", "SJC"].

Example 2: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] Return ["JFK","ATL","JFK","SFO","ATL","SFO"]. Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

题目地址： leetcode Reconstruct Itinerary

题意：给定一些飞机票，让你从中找出一个序列可以全部用完。要求如下

• 从JFK出发。
• 如果有多个解，输出字典序最小的。

思路：

这题其实很水，只要你这些数据结构掌握的好的话。

• 返回的答案必为n+1，n为tickets的个数

• 一张飞机票只能用一次，所以要计数。（可能重复）

• 字典序最小只需要保证我们遍历的时候从小到大遍历即可。so，建图的时候邻接表边从小到大。

  • 所以C++用map, Python 排序后OrderedDict.

以上所有的情况都考虑到了，然而没有1A我很惭愧。。。因为一时激动把DFS最后的return false 写成true了。。。

再ps: 题目其实可以增加难度的，比如，有的飞机票就是用不到啊[a,b ] [b,c] [f,g]最后一张用不到，让你求最多跑多少，多解输出最小序列。怎么实现就留给读者吧:)

C++

class Solution {
public:
	vector<string> findItinerary(vector<pair<string, string>> tickets) {
		unordered_map<string, map<string,int>> m;
		for (const auto &p : tickets) {
			m[p.first][p.second]++;
		}
		string start = "JFK";
		vector<string> ans;
		ans.push_back(start);
		dfs(start, ans, tickets.size()+ 1, m);
		return ans;
	}
	
	bool dfs(const string & cur,vector<string> &ans,const int &n,unordered_map<string, map<string, int>> &m) {
		if (ans.size() == n) return true;
		for (auto ticket = m[cur].begin(); ticket != m[cur].end(); ticket++) { //map<string, int>::iterator
			if (ticket->second != 0) {
				ticket->second--;
				ans.push_back(ticket->first);
				if (dfs(ticket->first, ans, n, m)) return true;
				ans.pop_back();
				ticket->second++;
			}
		}
		return false;
	}
};

 

Python

class Solution(object):
    def findItinerary(self, tickets):
        """
        :type tickets: List[List[str]]
        :rtype: List[str]
        """
        n, self.ans = len(tickets) + 1, ['JFK']
        m = collections.defaultdict(lambda :collections.OrderedDict())
        for x, y in sorted(tickets):
            m[x].setdefault(y,0)
            m[x][y] += 1
        self.dfs('JFK', n,m)
        return self.ans

    def dfs(self,cur,n,m):
            if len(self.ans) == n: return True
            if cur in m:
                for y,cnt in m[cur].items():
                    if cnt != 0:
                        m[cur][y], self.ans = m[cur][y] - 1, self.ans + [y]
                        if self.dfs(y,n,m): return True
                        m[cur][y], self.ans = m[cur][y] + 1, self.ans[:-1]
            return False

 

本题是leetcode 332  Reconstruct Itinerary 题解，

更多题解可以查看：https://www.hrwhisper.me/leetcode-algorithm-solution/