[leetcode] 336. Palindrome Pairs

[leetcode] 336. Palindrome Pairs

Description

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:

Input:

["abcd","dcba","lls","s","sssll"]

Output:

[[0,1],[1,0],[3,2],[2,4]]

Explanation:

The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]

Example 2:

Input:

["bat","tab","cat"]

Output:

[[0,1],[1,0]]

Explanation:

The palindromes are ["battab","tabbat"]

分析

题目的意思是：在字符数组中取两个串，使得能够组成回文子串。输出所有满足条件的组合情况。

要用到哈希表来建立每个单词和其位置的映射，然后需要一个set来保存出现过的单词的长度，算法的思想是，遍历单词集，对于遍历到的单词，对其翻转一下，然后在哈希表查找翻转后的字符串是否存在，注意不能和原字符串的坐标位置相同，因为有可能一个单词翻转后和原单词相等。现在只是处理了bat和tab的情况，还存在abcd和cba，dcb和abcd这些情况需要考虑，这就需要用set，由于set是自动排序的，可以找到当前单词长度在set中的iterator，然后从开头开始遍历set，遍历比当前单词小的长度，比如abcdd翻转后为ddcba，发现set中有长度为3的单词，然后判断dd是否为回文串，若是，再看cba是否存在于哈希表，若存在，则说明abcdd和cba是回文对，存入结果中；对于dcb和aabcd这类的情况也是同样处理，我们要在set里找的字符串要在遍历到的字符串的左边和右边分别尝试，看是否是回文对，这样遍历完单词集，就能得到所有的回文对。

代码

class Solution {public: vector> palindromePairs(vector& words) { vector> res; unordered_map m; set s; for(int i=0;i

参考文献

​​[LeetCode] Palindrome Pairs 回文对​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。