[LeetCode]Alien Dictionary

又是topological sorting的问题，但是这一题主要是建图比较麻烦。顶点就是每一个字母，edge从给定的 lexicographically sort里可以推断出来，我们首先比较首字母会得到一个序列，之后对于前缀相同的我们递归地比较之后的字母，直到比较完所有的后缀。之后根据这些序列来建图。之后就是普通的topological sorting了，假设字符不限于26个字母，有n个单词，平均长度k，时间复杂度O(V + E) = O(n * k + n * k) = O(n * k)，空间复杂度O(V + E) = O(n * k + n * k) = O(n * k)，代码如下：

	class Solution {
	public:
	string alienOrder(vector<string>& words) {
	vector<pair<int, int>> edges;
	if(!getEdges(words, edges, 0, words.size() - 1, 0))
	return "";
	unordered_map<int, vector<int>> g;
	unordered_map<int, int> indegrees;
	//indegree should contain all nodes
	for(auto& w : words)
	for(auto& c : w)
	indegrees[c] = 0;
	for(auto& e : edges)
	{
	g[e.first].emplace_back(e.second);
	++indegrees[e.second];
	}
	//get leaves
	queue<int> leaves;
	for(auto& p : indegrees)
	if(!p.second)
	leaves.push(p.first);
	//topological sorting
	string res;
	while(leaves.size())
	{
	int size = leaves.size();
	while(size-- > 0)
	{
	int c = leaves.front();
	leaves.pop();
	res += static_cast<char>(c);
	for(auto& next : g[c])
	if(--indegrees[next] == 0)
	leaves.push(next);
	}
	}
	//in case there is circle
	return res.size() == indegrees.size()? res: "";
	}
	private:
	bool getEdges(vector<string>& words, vector<pair<int, int>>& edges, int lo, int hi, int idx)
	{
	if(lo >= hi)return true;
	unordered_map<int, pair<int, int>> ranges;
	vector<int> seqs;
	for(int i = lo; i <= hi; ++i)
	{
	string w = words[i];
	if(idx >= w.size())
	continue;
	if(ranges.find(w[idx]) == ranges.end())
	{
	ranges[w[idx]] = {i, i};
	seqs.emplace_back(w[idx]);
	}
	else
	{
	//we have a circle here
	if(i - ranges[w[idx]].second > 1)
	return false;
	++ranges[w[idx]].second;
	}
	}
	//add edges
	for(int i = 0; i + 1 < seqs.size(); ++i)
	edges.emplace_back(seqs[i], seqs[i + 1]);
	//recursively process next index
	for(auto& range : ranges)
	if(!getEdges(words, edges, range.second.first, range.second.second, idx + 1))
	return false;
	return true;
	}
	};

view raw Alien Dictionary.cpp hosted with ❤ by GitHub