[LeetCode]Palindrome Pairs

思路其实很直观，对于每一个string找所有是palindrome的前缀和后缀，然后去map里找有没有string map剩余的部分。一般来讲，找所有palindrome前缀后缀的方法是一个一个看是不是palindrome，假设string长度为d，时间复杂度就为O(d^2)。但是我们有更好的方法，参考Shortest Palindrome中用KMP求最长回文前缀的方法，我们可以在O(n)的时间里找到所有的回文前后缀，注意去重即可。假设string平均长度为d，数量为n，时间复杂度为O(n * d)，代码如下：

	class Solution {
	public:
	vector<vector<int>> palindromePairs(vector<string>& words) {
	int len = words.size();
	vector<vector<int>> res;
	unordered_map<string, int> map;
	//we have to put all thing in map first, we can't update map while looking for pair, e.g. "lls" will look for "s" only in its turn, and "s" must be in the map to satisfy this
	for(int i = 0; i < len; ++i)
	map[words[i]] = i;
	for(int i = 0; i < len; ++i)
	{
	string s = words[i], rev = s;
	reverse(rev.begin(), rev.end());
	auto idx = palinPrefix(s + "#" + rev);
	for(int j : idx)
	{
	string target = s.substr(j);
	reverse(target.begin(), target.end());
	if(map.find(target) != map.end() && map[target] != i)
	res.push_back({map[target], i});
	}
	idx = palinPrefix(rev + "#" + s);
	for(int j : idx)
	{
	string target = rev.substr(j);
	//remove duplicate, we can't pair itself, or genereate result again(e.g. "abcd", "dcba") they will find each other as result in their turn, which generate duplicate
	if(map.find(target) != map.end() && map[target] != i && j)
	res.push_back({i, map[target]});
	}
	}
	return res;
	}
	private:
	//KMP find all palindrome prefix in linear time
	vector<int> palinPrefix(string s)
	{
	if(s.empty())return {};
	int i = 0, k = -1, len = s.size();
	vector<int> next(len + 1, -1);
	while(i < len)
	{
	if(k == -1 || s[k] == s[i])
	next[++i] = ++k;
	else
	k = next[k];
	}
	vector<int> idx;
	while(k != -1)
	{
	idx.push_back(k);
	k = next[k];
	}
	return idx;
	}
	};

view raw Palindrome Pairs.cpp hosted with ❤ by GitHub