leetcode 336. Palindrome Pairs

朴灿烈づ我的快乐病毒、 2022-07-30 20:53 42阅读 0赞

Given a list of unique words. Find all pairs of distinct indices `(i, j)` in the given list, so that the concatenation of the two words, i.e. `words[i] + words[j]` is a palindrome.

Example 1:  
Given `words` = `["bat", "tab", "cat"]`  
Return `[[0, 1], [1, 0]]`  
The palindromes are `["battab", "tabbat"]`

Example 2:  
Given `words` = `["abcd", "dcba", "lls", "s", "sssll"]`  
Return `[[0, 1], [1, 0], [3, 2], [2, 4]]`  
The palindromes are `["dcbaabcd", "abcddcba", "slls", "llssssll"]`

思路：对每个单词w，以w打头，在w末尾加那些单词e可以使w+e成为回文，再看以w为结尾，加那些单词e可以使e+w成为回文，检索e是否在字典中。为快速检索，将字典装到hashmap里。stl里普通的map是基于rb-tree的，unodoered\_map才是hash算法实现的，可以O(1)时间检索。

当前代码仍然可以优化的两个地方：

1.get\_patch函数里不用遍历整个s的长度，也不用check，判断一下可以提前结束

2.答案判重多余

class Solution {
    	bool check(string str)
    	{
    		int i = 0; int j = str.length() - 1;
    		while (i <= j && str[i] == str[j])
    		{
    			i++; j--;
    		}
    		if (i > j)
    			return true;
    		return false;
    	}
    	string reverse(string s, int i, int j)//[i,j]闭区间，从0开始
    	{
    		string ss;
    		for (int h = j; h >= i; h--)
    			ss += s[h];
    		return ss;
    	}
    	vector<string>get_patch(string &s)
    	{
    		vector<string>rr;
    		rr.push_back(reverse(s, 0, s.length() - 1));
    		rr.push_back(reverse(s, 0, s.length() - 2));
    		int k = s.length() - 2;
    		while (k >= 1)
    		{
    			if (k-1>=0&&s[k + 1] == s[k - 1])
    			{
    				if (check(s + reverse(s, 0, k -1- (s.length() - 1 - k))))
    				rr.push_back(reverse(s, 0, k -1- (s.length() - 1 - k)));
    			}
    			if (s[k] == s[k + 1])
    			{
    				if (check(s + reverse(s, 0, k -1- (s.length() - 1 - k - 1))))
    					rr.push_back(reverse(s, 0, k -1- (s.length() - 1 - k - 1)));
    			}
    			k--;
    		}
    		return rr;
    	}
    public:
    	vector<vector<int>> palindromePairs(vector<string>& words) {
    		set<vector<int>>re;
    		unordered_map<string, int>hashword;
    		bool flag = false;
    		int index = -1;
    		for (int i = 0; i < words.size(); i++)
    		{
    			hashword[words[i]] = i;
    			if (words[i] == "")
    			{
    				flag = true;
    				index = i;
    			}
    		}
    		for (int i = 0; i < words.size(); i++)
    		{
    			if (flag&&check(words[i])&&i!=index)
    			{
    				vector<int>cc; cc.push_back(i); cc.push_back(index);
    				re.insert(cc);
    				cc.clear(); cc.push_back(index); cc.push_back(i);
    				re.insert(cc);
    			}
    			vector<string>ss = get_patch(words[i]);
    			for (int j = 0; j < ss.size();j++)
    				if (hashword.find(ss[j]) != hashword.end() && hashword[ss[j]] != i)
    				{
    				vector<int>cc; cc.push_back(i); cc.push_back(hashword[ss[j]]);
    				re.insert(cc);
    				}
    			string rs = reverse(words[i], 0, words[i].length() - 1);
    			ss = get_patch(rs);
    			for (int j = 0; j < ss.size(); j++)
    			{
    				string str = reverse(ss[j], 0, ss[j].length() - 1);
    				if (hashword.find(str) != hashword.end() && hashword[str] != i)
    				{
    					vector<int>cc; cc.push_back(hashword[str]); cc.push_back(i);
    					re.insert(cc);
    				}
    			}
    		}
    		return vector<vector<int>>(re.begin(),re.end());
    	}
    };