首页 > 代码库 > Palindrome Pairs
Palindrome Pairs
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"]
class Solution {private: bool isPalindrome(string s) { int left = 0; int right = s.length() - 1; while (left < right) { if (s[left++] != s[right--]) return false; } return true; }public: vector<vector<int>> palindromePairs(vector<string>& words) { vector<vector<int>> ret; unordered_map<string, int> dict; int size = words.size(); for (int i = 0; i < size; i++) { string key = words[i]; reverse(key.begin(), key.end()); dict[key] = i; } if (dict.find("") != dict.end()) { for (int i = 0; i < size; i++) { if (i == dict[""]) continue; if (isPalindrome(words[i])) ret.push_back( { dict[""], i }); } } for (int i = 0; i < size; i++) { for (int j = 0; j < words[i].size(); j++) { string left = words[i].substr(0, j); string right = words[i].substr(j, words[i].size() - j); if (dict.find(left) != dict.end() && isPalindrome(right) && dict[left] != i) { ret.push_back( { i, dict[left] }); } if (dict.find(right) != dict.end() && isPalindrome(left) && dict[right] != i) { ret.push_back( { dict[right], i }); } } } return ret; }};
Palindrome Pairs
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。