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 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.


给定一系列机票,每张机票标明了A→B的一段旅程,现在要求把所有的机票旅程连成一条完整的长距离航线,要求起点是JFK。如果有多条合法的航线,则输出字典序最小的那条。

显然要转换为图的问题,每个机场转换为一个点,每张机票转换为一条边,然后从JFK开始DFS,保留每条合法的航线,然后sort取字典序最小的航线。

把问题转换为图不难,使用hash给每个机场编号,然后新建一个图。在图中以JFK开始DFS也不难,每深入DFS一层,机票数目减1,当机票数目为0时,DFS结束,找到一条合法航线。

我一开始是这么做的,但是TLE了,因为这样可能会进行很多次DFS, 找到多条航线,还需要sort取字典序最小的航线。

有没有办法一次找到字典序最小的航线呢,只需要在DFS的时候,每次都从字典序最小的机场开始下一层DFS,这样第一次DFS成功的航线肯定是字典序最小的航线。

所以我们给机场编号的时候,先使用map记录,map会自动按key的字典序从小到大排好。然后遍历map重新编号,并且用hash2记录编号和机场的对应关系。这样,在DFS的时候,从0→n的遍历,就自动是按字典序从小到大遍历。

代码如下:

class Solution {
private:
	bool dfs(string& ans, vector<string>& hash2, vector<vector<int>>& graph, int start, int lines) {
		if (lines == 0) return true;
		int n = hash2.size();
		for (int i = 0; i < n; ++i) { // 字典序从小到大深搜
			if (graph[start][i] > 0) {
				--graph[start][i];
				ans += hash2[i];
				if (dfs(ans, hash2, graph, i, lines - 1))return true;
				++graph[start][i];
				ans = ans.substr(0, ans.size() - 3);
			}
		}
		return false;
	}
public:
	vector<string> findItinerary(vector<pair<string, string>> tickets) {
		map<string, int> hash1;
		vector<string> hash2;
		int cnt = 0, n = tickets.size();
		for (int i = 0; i < tickets.size(); ++i) { // 记录
			hash1[tickets[i].first] = 0;
			hash1[tickets[i].second] = 0;
		}
		for (auto it = hash1.begin(); it != hash1.end(); ++it) {
			it->second = cnt++; // 字典序从小到大编号
			hash2.push_back(it->first);
		}

		vector<vector<int>> graph(cnt, vector<int>(cnt, 0)); // 构图
		for (int i = 0; i < tickets.size(); ++i)++graph[hash1[tickets[i].first]][hash1[tickets[i].second]];
		
		int start = hash1["JFK"];
		string ans = "JFK";
		dfs(ans, hash2, graph, start, n); // 深搜

		vector<string> Itinerary;
		for (int i = 0; i <= ans.size() - 3; i += 3)Itinerary.push_back(ans.substr(i, 3));
		
		return Itinerary;
	}
};

本代码提交AC,用时22MS。

Leave a Reply

Your email address will not be published. Required fields are marked *