Hard

题目描述

给定一个由唯一字符串组成的数组 words。

回文对是一对整数 (i, j)，满足以下条件：

  • 0 <= i, j < words.length
  • i != j
  • words[i] + words[j]（两个字符串的连接）是一个回文串

返回 words 的所有回文对。

你必须设计一个时间复杂度为 O(所有 words[i].length 的总和) 的算法。

示例 1：

输入：words = ["abcd","dcba","lls","s","sssll"]
输出：[[0,1],[1,0],[3,2],[2,4]]
解释：回文串为 ["abcddcba","dcbaabcd","slls","llssssll"]

示例 2：

输入：words = ["bat","tab","cat"]
输出：[[0,1],[1,0]]
解释：回文串为 ["battab","tabbat"]

示例 3：

输入：words = ["a",""]
输出：[[0,1],[1,0]]
解释：回文串为 ["a","a"]

提示：

  • 1 <= words.length <= 5000
  • 0 <= words[i].length <= 300
  • words[i] 由小写英文字母组成

解题思路

这道题要求在 O(总字符数) 时间复杂度内找到所有回文对，暴力枚举所有配对会超时。

核心思路： 使用哈希表优化查找过程。对于每个单词，我们考虑它作为回文串的后缀，然后查找能作为前缀的单词。

关键观察： 如果 words[i] + words[j] 是回文串，那么存在三种情况：

  1. len(words[i]) == len(words[j])：words[i] 是 words[j] 的反转
  2. len(words[i]) < len(words[j])：words[j] 的前缀是 words[i] 的反转，且 words[j] 的剩余部分是回文
  3. len(words[i]) > len(words[j])：words[i] 的后缀是 words[j] 的反转，且 words[i] 的剩余部分是回文

算法步骤：

  1. 建立哈希表，存储每个单词及其索引
  2. 对每个单词，枚举所有可能的分割点
  3. 检查分割后的部分是否能与哈希表中的单词组成回文对
  4. 特别处理空字符串的情况

这种方法避免了 O(n²) 的枚举，通过哈希表将查找时间降到 O(1)，总时间复杂度为 O(所有单词长度之和)。

代码实现

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        unordered_map<string, int> wordMap;
        vector<vector<int>> result;
        
        // 建立单词到索引的映射
        for (int i = 0; i < words.size(); i++) {
            wordMap[words[i]] = i;
        }
        
        for (int i = 0; i < words.size(); i++) {
            string word = words[i];
            int n = word.length();
            
            // 枚举所有可能的分割点
            for (int j = 0; j <= n; j++) {
                string prefix = word.substr(0, j);
                string suffix = word.substr(j);
                
                // 情况1: prefix是回文，查找suffix的反转
                if (isPalindrome(prefix)) {
                    string reverseSuffix = suffix;
                    reverse(reverseSuffix.begin(), reverseSuffix.end());
                    if (wordMap.count(reverseSuffix) && wordMap[reverseSuffix] != i) {
                        result.push_back({wordMap[reverseSuffix], i});
                    }
                }
                
                // 情况2: suffix是回文，查找prefix的反转
                if (j != n && isPalindrome(suffix)) {
                    string reversePrefix = prefix;
                    reverse(reversePrefix.begin(), reversePrefix.end());
                    if (wordMap.count(reversePrefix) && wordMap[reversePrefix] != i) {
                        result.push_back({i, wordMap[reversePrefix]});
                    }
                }
            }
        }
        
        return result;
    }
    
private:
    bool isPalindrome(const string& s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }
};

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        def is_palindrome(s):
            return s == s[::-1]
        
        word_map = {word: i for i, word in enumerate(words)}
        result = []
        
        for i, word in enumerate(words):
            n = len(word)
            
            # 枚举所有可能的分割点
            for j in range(n + 1):
                prefix = word[:j]
                suffix = word[j:]
                
                # 情况1: prefix是回文，查找suffix的反转
                if is_palindrome(prefix):
                    reverse_suffix = suffix[::-1]
                    if reverse_suffix in word_map and word_map[reverse_suffix] != i:
                        result.append([word_map[reverse_suffix], i])
                
                # 情况2: suffix是回文，查找prefix的反转
                if j != n and is_palindrome(suffix):
                    reverse_prefix = prefix[::-1]
                    if reverse_prefix in word_map and word_map[reverse_prefix] != i:
                        result.append([i, word_map[reverse_prefix]])
        
        return result

public class Solution {
    public IList<IList<int>> PalindromePairs(string[] words) {
        var wordMap = new Dictionary<string, int>();
        var result = new List<IList<int>>();
        
        // 建立单词到索引的映射
        for (int i = 0; i < words.Length; i++) {
            wordMap[words[i]] = i;
        }
        
        for (int i = 0; i < words.Length; i++) {
            string word = words[i];
            int n = word.Length;
            
            // 枚举所有可能的分割点
            for (int j = 0; j <= n; j++) {
                string prefix = word.Substring(0, j);
                string suffix = word.Substring(j);
                
                // 情况1: prefix是回文，查找suffix的反转
                if (IsPalindrome(prefix)) {
                    string reverseSuffix = new string(suffix.Reverse().ToArray());
                    if (wordMap.ContainsKey(reverseSuffix) && wordMap[reverseSuffix] != i) {
                        result.Add(new List<int> { wordMap[reverseSuffix], i });
                    }
                }
                
                // 情况2: suffix是回文，查找prefix的反转
                if (j != n && IsPalindrome(suffix)) {
                    string reversePrefix = new string(prefix.Reverse().ToArray());
                    if (wordMap.ContainsKey(reversePrefix) && wordMap[reversePrefix] != i) {
                        result.Add(new List<int> { i, wordMap[reversePrefix] });
                    }
                }
            }
        }
        
        return result;
    }
    
    private bool IsPalindrome(string s) {
        int left = 0, right = s.Length - 1;
        while (left < right) {
            if (s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }
}

var palindromePairs = function(words) {
    const isPalindrome = (s) => {
        let left = 0, right = s.length - 1;
        while (left < right) {
            if (s[left] !== s[right]) return false;
            left++;
            right--;
        }
        return true;
    };
    
    const wordMap = new Map();
    const result = [];
    
    // 建立单词到索引的映射
    for (let i = 0; i < words.length; i++) {
        wordMap.set(words[i], i);
    }
    
    for (let i = 0; i < words.length; i++) {
        const word = words[i];
        const n = word.length;
        
        // 枚举所有可能的分割点
        for (let j = 0; j <= n; j++) {
            const prefix = word.substring(0, j);
            const suffix = word.substring(j);
            
            // 情况1: prefix是回文，查找suffix的反转
            if (isPalindrome(prefix)) {
                const reverseSuffix = suffix.split('').reverse().join('');
                if (wordMap.has(reverseSuffix) && wordMap.get(reverseSuffix) !== i) {
                    result.push([wordMap.get(reverseSuffix), i]);
                }
            }
            
            // 情况2: suffix是回文，查找prefix的反转
            if (j !== n && isPalindrome(suffix)) {
                const reversePrefix = prefix.split('').reverse().join('');
                if (wordMap.has(reversePrefix) && wordMap.get(reversePrefix) !== i) {
                    result.push([i, wordMap.get(reversePrefix)]);
                }
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(∑(words[i].length)²)对每个单词的每个分割点都要检查回文，最坏情况下为所有单词长度平方和
空间复杂度O(∑(words[i].length))哈希表存储所有单词，空间为所有单词长度之和

相关题目