摘要:描述給定一組唯一的單詞,找出所有不同的索引對,使得列表中的兩個單詞,,可拼接成回文串。遍歷每一個單詞,對每一個單詞進行切片,組成和。
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
源代碼文件在 這里 。
?本文首發于 何睿的博客 ,歡迎轉載,轉載需保留 文章來源 ,作者信息和本聲明.
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/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復雜度因為用了額外的來儲存,需要空間。時間復雜度每個分為兩個部分,調用前后兩部分總長度為所以每次調用為一共次。 Given a list of unique words, find all pairs of distinct indices (i, j) in the g...
摘要:和的區別是,所以對于,效率更高不允許作為鍵值,而允許一個鍵和無限個值有一個,叫,便于查詢可預測的迭代順序。這道題依然選擇的話 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...
摘要:部分是回文的,在里面找是否有的。這里的范圍是,最小是,因為要保證是兩個單詞,最大是,這時候要找出另一個和他相反的串。判斷為回文,可以直接暴力,每個都判斷一次。兩個方向都找一遍就可能出現重復的情況,注意避免重復。例如,結果應該是。 Palindrome Pairs 鏈接:https://leetcode.com/problems... 這道題沒想出來思路,參考了這個博客的內容:http:...
摘要:前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫~現在翻起來覺得蠻亂的??赡艽蠹铱粗卜浅2环奖恪K栽谶@里做個索引嘻嘻。 順序整理 1~50 1...
閱讀 781·2021-11-09 09:47
閱讀 1568·2019-08-30 15:44
閱讀 1143·2019-08-26 13:46
閱讀 2107·2019-08-26 13:41
閱讀 1266·2019-08-26 13:32
閱讀 3772·2019-08-26 10:35
閱讀 3519·2019-08-23 17:16
閱讀 448·2019-08-23 17:07