LeetCode 336. Palindrome Pairs

TigerChain 发布于2019-07-31 10:16 / 2545人阅读

摘要：描述给定一组唯一的单词，找出所有不同的索引对，使得列表中的两个单词，，可拼接成回文串。遍历每一个单词，对每一个单词进行切片，组成和。

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"]

描述

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

示例 1:

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

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

思路

构建字典，字典的键为单词，值为单词的索引。

遍历每一个单词，对每一个单词进行切片，组成 prefix 和 subfix。

如果 prefix 本身是回文字符串，我们检查 subfix 的反转是否在字典中，如果在，说明可以构成一个满足题意的回文字符串，我们将该键的值，当前单词的索引构成一个组合（注意顺序）。

如果 subfix 是一回文字符串，我们检查 prefix 的反抓是否在字典中，如果在，说明可以构成一个满足题意的回文字符串，我们将当前单词的索引，该键的值构成一个组个（注意顺序）

注意在检查回文字符串的时候，注意重复。

# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-04-06 12:11:30
# @Last Modified by:   何睿
# @Last Modified time: 2019-04-07 10:20:01


class Solution:
    def palindromePairs(self, words: [str]) -> [[int]]:
        # 结果数组
        result = []
        # 字典，用于获取索引
        worddict = {word: i for i, word in enumerate(words)}
        for i, word in enumerate(words):
            count = len(word)
            for j in range(count + 1):
                # 获取字段的前半部分，后半部分
                prefix, subfix = word[:j], word[j:]
                # 前半部分的反转，后半部分的反转
                reprefix, resubfix = prefix[::-1], subfix[::-1]
                # 如果前半部分是 palindrome 并且后半部分的反转在字典中
                if prefix == reprefix and resubfix in worddict:
                    m = worddict[resubfix]
                    # 不能取到字符本身
                    if m != i: result.append([m, i])
                # 如果后半部分是回文字符串，并且前半部分的逆序在字典中
                if j != count and subfix == resubfix and reprefix in worddict:
                    result.append([i, worddict[reprefix]])
        return result

源代码文件在这里。
©本文首发于何睿的博客，欢迎转载，转载需保留文章来源，作者信息和本声明.

云服务器 GPU云服务器 pairs palindrome 云主机336 LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/43543.html

[LeetCode] 336. Palindrome Pairs

Problem 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: Inpu...

lentoo 2019-08-16 13:45 评论0 收藏0
336. Palindrome Pairs

摘要：容易出的两个地方以为例。这两个互为的在尾部加上也就是在头部加上所以后部分不能为空，否则就和头部为空的情况重复了。空间复杂度因为用了额外的来储存，需要空间。时间复杂度每个分为两个部分，调用前后两部分总长度为所以每次调用为一共次。 Given a list of unique words, find all pairs of distinct indices (i, j) in the g...

Guakin_Huang 2019-08-14 17:57 评论0 收藏0
[LeetCode] Palindrome Pairs

摘要：和的区别是，所以对于，效率更高不允许作为键值，而允许一个键和无限个值有一个，叫，便于查询可预测的迭代顺序。这道题依然选择的话 Problem Given a list of unique words. Find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the...

DangoSky 2019-08-14 15:47 评论0 收藏0
Palindrome Pairs & Shortest Palindrome

摘要：部分是回文的，在里面找是否有的。这里的范围是，最小是，因为要保证是两个单词，最大是，这时候要找出另一个和他相反的串。判断为回文，可以直接暴力，每个都判断一次。两个方向都找一遍就可能出现重复的情况，注意避免重复。例如，结果应该是。 Palindrome Pairs 链接：https://leetcode.com/problems... 这道题没想出来思路，参考了这个博客的内容：http:...

CNZPH 2019-08-14 17:20 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0