专栏首页SnailTyanLeetcode 336. Palindrome Pairs

Leetcode 336. Palindrome Pairs

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书

1. Description

2. Solution

解析:Version 1简单,容易理解,但超时。Version 2是将字符串分为两部分,前半部分和后半部分,如果两部分有一部分是回文子串,则寻找另一部分的对应的回文字符串。

  • Version 1
class Solution:
    def palindromePairs(self, words):
        result = []
        length = len(words)
        for i in range(length):
            for j in range(i + 1, length):
                positive = words[i] + words[j]
                reverse = words[j] + words[i]
                if self.checkPalindrome(positive):
                    result.append([i, j])
                if self.checkPalindrome(reverse):
                    result.append([j, i])
        return result


    def checkPalindrome(self, word):
        i = 0
        j = len(word) - 1
        while i < j:
            if word[i] != word[j]:
                return False
            i += 1
            j -= 1
        return True
  • Version 2
class Solution:
    def palindromePairs(self, words):
        result = []
        stat = {}
        for index, word in enumerate(words):
            stat[word] = index

        for index, word in enumerate(words):
            length = len(word)
            if length == 1 and '' in stat:
                result.append([index, stat['']])
                result.append([stat[''], index])
                continue
            for i in range(length + 1):
                prefix = word[:i]
                rest = word[i:]
                reverse = rest[::-1]
                if self.checkPalindrome(prefix):
                    if reverse in stat and index != stat[reverse]:
                        res = [stat[reverse], index]
                        if res not in result:
                            result.append(res)

                suffix = word[i:]
                rest = word[:i]
                reverse = rest[::-1]
                if self.checkPalindrome(suffix):
                    
                    if reverse in stat and index != stat[reverse]:
                        res = [index, stat[reverse]]
                        if res not in result:
                            result.append(res)

        return result


    def checkPalindrome(self, word):
        i = 0
        j = len(word) - 1
        while i < j:
            if word[i] != word[j]:
                return False
            i += 1
            j -= 1
        return True

Reference

  1. https://leetcode.com/problems/palindrome-pairs/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • CodeForces 17E Palisection(回文树)

    E. Palisection time limit per test 2 seconds memory limit per test 128 meg...

    ShenduCC
  • Leetcode 题目列表(难度、出现频率、知识点)

    不全,但好像没看到有更好的版本,刷前132题暂时凑合着用吧! 转载自:LeetCode Question Difficulty Distribution ?...

    triplebee
  • LeetCode-9. Palindrome Number | 回文数

    Given an integer x, return true if x is palindrome integer.

    Zoctopus
  • HDU 5157 Harry and magic string(回文树)

    Harry and magic string Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: ...

    ShenduCC
  • LeetCode-Longest Palindromic Substring

    LeetCode第5道题目:5. Longest Palindromic Substring

    卡尔曼和玻尔兹曼谁曼
  • LeetCode 分类刷题 —— Linked List

    最近有朋友问我怎么没有更新文章了,因为最近有空的时候都在刷 LeetCode,零零星星刷了快 2 个月了,也累积了不少题目了,所以最近打算把做的几百道题归类,总...

    一缕殇流化隐半边冰霜
  • 【LeetCode 409】 关关的刷题日记31Longest Palindrome

    关关的刷题日记31 – Leetcode 409. Longest Palindrome 题目 Given a string which consists o...

    WZEARW
  • LeetCode刷题指南(字符串)

    文章链接:https://github.com/CyC2018/CS-Notes/blob/master/docs/notes/Leetcode%20%E9%A...

    黄小斜学Java
  • 算法养成记:回文数判断

    Determine whether an integer is a palindrome. An integer is a palindrome when it...

    三哥

扫码关注云+社区

领取腾讯云代金券