資訊專欄INFORMATION COLUMN
摘要：描述給定一組唯一的單詞，找出所有不同的索引對(duì)，使得列表中的兩個(gè)單詞，，可拼接成回文串。遍歷每一個(gè)單詞，對(duì)每一個(gè)單詞進(jìn)行切片，組成和。
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"]
給定一組唯一的單詞， 找出所有不同 的索引對(duì)(i, j)，使得列表中的兩個(gè)單詞， 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"]
構(gòu)建字典，字典的鍵為單詞，值為單詞的索引。
遍歷每一個(gè)單詞，對(duì)每一個(gè)單詞進(jìn)行切片，組成 prefix 和 subfix。
如果 prefix 本身是回文字符串，我們檢查 subfix 的反轉(zhuǎn)是否在字典中，如果在，說明可以構(gòu)成一個(gè)滿足題意的回文字符串，我們將該鍵的值，當(dāng)前單詞的索引構(gòu)成一個(gè)組合（注意順序）。
如果 subfix 是一回文字符串，我們檢查 prefix 的反抓是否在字典中，如果在，說明可以構(gòu)成一個(gè)滿足題意的回文字符串，我們將當(dāng)前單詞的索引，該鍵的值構(gòu)成一個(gè)組個(gè)（注意順序）
注意在檢查回文字符串的時(shí)候，注意重復(fù)。
# -*- 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]]:
# 結(jié)果數(shù)組
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:]
# 前半部分的反轉(zhuǎn)，后半部分的反轉(zhuǎn)
reprefix, resubfix = prefix[::-1], subfix[::-1]
# 如果前半部分是 palindrome 并且后半部分的反轉(zhuǎn)在字典中
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
源代碼文件在 這里 。
?本文首發(fā)于 何睿的博客 ，歡迎轉(zhuǎn)載，轉(zhuǎn)載需保留 文章來源 ，作者信息和本聲明.
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/43543.html
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...
摘要：容易出的兩個(gè)地方以為例。這兩個(gè)互為的在尾部加上也就是在頭部加上所以后部分不能為空，否則就和頭部為空的情況重復(fù)了?？臻g復(fù)雜度因?yàn)橛昧祟~外的來儲(chǔ)存，需要空間。時(shí)間復(fù)雜度每個(gè)分為兩個(gè)部分，調(diào)用前后兩部分總長度為所以每次調(diào)用為一共次。 Given a list of unique words, find all pairs of distinct indices (i, j) in the g...
摘要：和的區(qū)別是，所以對(duì)于，效率更高不允許作為鍵值，而允許一個(gè)鍵和無限個(gè)值有一個(gè)，叫，便于查詢可預(yù)測的迭代順序。這道題依然選擇的話 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...
摘要：部分是回文的，在里面找是否有的。這里的范圍是，最小是，因?yàn)橐ＷC是兩個(gè)單詞，最大是，這時(shí)候要找出另一個(gè)和他相反的串。判斷為回文，可以直接暴力，每個(gè)都判斷一次。兩個(gè)方向都找一遍就可能出現(xiàn)重復(fù)的情況，注意避免重復(fù)。例如，結(jié)果應(yīng)該是。 Palindrome Pairs 鏈接：https://leetcode.com/problems... 這道題沒想出來思路，參考了這個(gè)博客的內(nèi)容：http:...
摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個(gè)索引嘻嘻。 順序整理 1~50 1...
閱讀 789·2021-11-09 09:47
閱讀 1581·2019-08-30 15:44
閱讀 1149·2019-08-26 13:46
閱讀 2114·2019-08-26 13:41
閱讀 1279·2019-08-26 13:32
閱讀 3783·2019-08-26 10:35
閱讀 3532·2019-08-23 17:16
閱讀 462·2019-08-23 17:07
