回文对

336. 回文对

给定一组 互不相同 的单词，找出所有不同的索引对 (i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。

示例 1：

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

示例 2：

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

示例 3：

输入：words = ["a",""]
输出：[[0,1],[1,0]]

提示：

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

相似题目

最长回文子串

最短回文串

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<vector<int>> palindromePairs(vector<string>& words) { } };

golang 解法, 执行用时: 1372 ms, 内存消耗: 12.1 MB, 提交时间: 2023-06-08 09:54:15

func palindromePairs(words []string) [][]int {
	ret := make([][]int, 0)
	wordsMap := make(map[string]int)
	for i := 0; i < len(words); i++ {
		wordsMap[words[i]] = i
	}
	for i := 0; i < len(words); i++ {
		for j := 0; j < len(words[i])+1; j++ {
			pre, suf := words[i][:j], words[i][j:]                                  // 出现重复解，寻找长度等于它自身长度的匹配时
			if v, ok := wordsMap[reverse(pre)]; ok && v != i && isPalindrome(suf) { // pre为翻转，suf为回文
				ret = append(ret, []int{i, v})
			}
			// 在suf为翻转时加上j > 0剔除j=0的情况，j=0时pre为空，suf为其本身，避免重复解(在上一个if中加上j < len(words[i]同理)
			if v, ok := wordsMap[reverse(suf)]; ok && v != i && j > 0 && isPalindrome(pre) { // pre为回文，suf为翻转
				ret = append(ret, []int{v, i})
			}
		}
	}
	return ret
}

func isPalindrome(s string) bool {
	l, r := 0, len(s)-1
	for l < r {
		if s[l] != s[r] {
			return false
		}
		l++
		r--
	}
	return true
}

func reverse(s string) string {
	b := []byte(s)
	for i := 0; i < len(b)/2; i++ {
		b[i], b[len(b)-1-i] = b[len(b)-1-i], b[i]
	}
	return string(b)
}

golang 解法, 执行用时: 904 ms, 内存消耗: 19.1 MB, 提交时间: 2023-06-08 09:53:20

func isPalindrome(s string) bool {
    for i := 0; i < len(s) / 2; i++ {
        if s[i] != s[len(s)-i-1] {
            return false
        }
    }
    return true
}

func reverse(s string) string {
    ans := []byte{}

    for i := len(s) - 1; i >= 0; i-- {
        ans = append(ans, s[i])
    }
    return string(ans)
}

func palindromePairs(words []string) [][]int {
    rh := make(map[string]int)
    h := make(map[string]int)
    for i, v := range words {
        rh[reverse(v)] = i
        h[v] = i
    }

    ans := [][]int{}
    for i, v := range words {
        for j := 0; j < len(v); j++ {
            //分成t1, t2两个子串
            t1 := v[0:j]
            t2 := v[j:]
            //t1是子串的情况下
            if isPalindrome(t2) {
                if v, ok := rh[t1]; ok && v != i {
                    ans = append(ans, []int{i, v})
                    if t1 == "" {
                        ans = append(ans, []int{v, i})
                    }     
                }
            }
            if isPalindrome(t1) {
                if v, ok := h[reverse(t2)]; ok && v != i {
                    ans = append(ans, []int{v, i})
                }
            }
        }
    }
    return ans
}

python3 解法, 执行用时: 2464 ms, 内存消耗: 26.6 MB, 提交时间: 2023-06-08 09:52:41

class Solution:
    def get_palindrome_parts(self,str):
        pre,suf = [],[]
        lenstr = len(str)
        for i in range(0,lenstr + 1):
            #前缀是回文,包括单词本身
            if str[:i] == str[:i][::-1]:
                pre.append(str[i:][::-1])
            #后缀是回文,包括单词本身
            if str[i:] == str[i:][::-1]:
                suf.append(str[:i][::-1])
        return pre,suf
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        dataset = {w: i for i, w in enumerate(words)}
        res = []
        for index,word in enumerate(words):
            pre,suf = self.get_palindrome_parts(word)
            for p in pre:
                #p[::-1] != word 前缀判断中过滤掉单词本身与其他单词形成回文的情况，避免在后缀判断中重复
                #index != dataset[p] 如果是单词本身则不处理
                if p in dataset and index != dataset[p] and p[::-1] != word:
                    res.append([dataset[p],index])
            for s in suf:
                if s in dataset and index != dataset[s]:
                    res.append([index,dataset[s]])
        return res

python3 解法, 执行用时: 1960 ms, 内存消耗: 371.5 MB, 提交时间: 2023-06-08 09:52:28

class Trie:
    def __init__(self):
        self.dct = dict()

    def add(self, word, i):
        cur = self.dct
        for va in word:
            if va not in cur:
                cur[va] = dict()
            cur = cur[va]
        cur['isEnd'] = i
        return


class Solution:
    def palindromePairs(self, words):
        
        # 按照长度进行排序
        n = len(words)
        for i in range(n):
            words[i] = [words[i], i]
        words.sort(key=lambda x: [len(x[0]), x[0]])
        
        # 正反字典树
        trie = Trie()
        trie_rev = Trie()

        def check(l, r):
            while l < r:
                if word[r] == word[l]:
                    l += 1
                    r -= 1
                else:
                    break
            return l >= r

        res = []
        for word, i in words:
            m = len(word)
            # 当前字符在后面
            cur = trie.dct
            j = m-1
            search = True
            while j >= 0:
                if 'isEnd' in cur and check(0, j):
                    res.append([cur['isEnd'], i])
                if word[j] in cur:
                    cur = cur[word[j]]
                    j -= 1
                else:
                    search = False
                    break
            if search and 'isEnd' in cur and check(0, j):
                res.append([cur['isEnd'], i])
            trie.add(word, i)

            # 当前字符在前面
            cur = trie_rev.dct
            j = 0
            search = True
            while j <= m-1:
                if 'isEnd' in cur and check(j, m-1):
                    res.append([i, cur['isEnd']])
                if word[j] in cur:
                    cur = cur[word[j]]
                    j += 1
                else:
                    search = False
                    break
            if search and 'isEnd' in cur and check(j, m-1):
                res.append([i, cur['isEnd']])
            trie_rev.add(word[::-1], i)
        return res

python3 解法, 执行用时: 2252 ms, 内存消耗: 26.5 MB, 提交时间: 2023-06-08 09:52:15

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:

        # 核心思想--枚举前缀和后缀
        # 如果两个字符串k1，k2组成一个回文字符串会出现三种情况
        # len(k1) == len(k2),则需要比较k1 == k2[::-1]
        # len(k1) < len(k2),例如，k1=a, k2=abb,可组成abba
        #   因为k2后缀bb已经是回文字符串了，则需要找k1与k2剩下相等的部分
        # len(k1) > len(k2),例如，k1=bba, k2=a,组成abba
        #   因为k1前缀bb已经是回文字符串了，则需要找k1剩下与k2相等的部分

        res = []
        worddict = {word: i for i, word in enumerate(words)}  # 构建一个字典，key为word，valie为索引
        for i, word in enumerate(words):
            # i为word索引，word为字符串
            for j in range(len(word)+1): 
                # 这里+1是因为，列表切片是前闭后开区间
                tmp1 = word[:j]  # 字符串的前缀
                tmp2 = word[j:]  # 字符串的后缀
                if tmp1[::-1] in worddict and worddict[tmp1[::-1]] != i and tmp2 == tmp2[::-1]:
                    # 当word的前缀在字典中，且不是word自身，且word剩下部分是回文(空也是回文)
                    # 则说明存在能与word组成回文的字符串
                    res.append([i, worddict[tmp1[::-1]]])  # 返回此时的word下标和找到的字符串下标

                if j > 0 and tmp2[::-1] in worddict and worddict[tmp2[::-1]] != i and tmp1 == tmp1[::-1]:         
                    # 当word的后缀在字典中，且不是word自身，且word剩下部分是回文(空也是回文)
                    # 则说明存在能与word组成回文的字符串
                    # 注意：因为是后缀，所以至少要从word的第二位算起，所以j>0
                    res.append([worddict[tmp2[::-1]], i])  # 返回此时的word下标和找到的字符串下标
        return res

javascript 解法, 执行用时: 2020 ms, 内存消耗: 62.1 MB, 提交时间: 2023-06-08 09:50:11

/**
 * @param {string[]} words
 * @return {number[][]}
 */
const palindromePairs = (words) => {
  const reverseds = new Map();
  for (let i = 0; i < words.length; i++) {
    const reversed = words[i].split('').reverse().join('');
    reverseds.set(reversed, i);
  }
  const res = [];
  for (let i = 0; i < words.length; i++) {
    const curWord = words[i];
    if (isPalindrome(curWord) && reverseds.has('') && curWord !== '') {
      res.push([reverseds.get(''), i]);
    }
    for (let j = 0; j < curWord.length; j++) {
      const left = curWord.substring(0, j);
      const right = curWord.substring(j);
      if (isPalindrome(left) && reverseds.has(right) && reverseds.get(right) !== i) {
        res.push([reverseds.get(right), i]);
      }
      if (isPalindrome(right) && reverseds.has(left) && reverseds.get(left) !== i) {
        res.push([i, reverseds.get(left)]);
      }
    }
  }
  return res;
};

/**
 * @param {string} str
 * @return {boolean}
 */
const isPalindrome = (str) => {
  let l = 0, r = str.length - 1;
  while (l < r) {
    if (str[l++] != str[r--]) return false; // 我很不想这么写，尽量一句话做一件事吧
  }
  return true;
};

python3 解法, 执行用时: 2048 ms, 内存消耗: 26.5 MB, 提交时间: 2023-06-08 09:47:42

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        a = {w:i for i, w in enumerate(words)}
        return sum(([[i, a[w[::-1]]], [a[w[::-1]], i]]for i, w in enumerate(words) if w[::-1] in a and a[w[::-1]] < i), []) + (sum(([[j,a[""]], [a[""], j]] for j, s in enumerate(words) if s == s[::-1] and j != a[""]) , []) if "" in a else []) + [[i, a[w[:k][::-1]]] for i, w in enumerate(words) for k in range(1, len(w)) if w[:k][::-1] in a and w[k:] == w[k:][::-1] and i!= a[w[:k][::-1]]] + [[a[w[k:][::-1]], i] for i, w in enumerate(words) for k in range(1, len(w)) if w[k:][::-1] in a and w[:k] == w[:k][::-1] and i!= a[w[k:][::-1]]]

上一题

下一题

详情