LeetCode 솔루션 분류
[9/17] 336. Palindrome Pairs
본문
Hard
3471345Add to ListShareGiven a list of unique words, return all the pairs of the distinct indices (i, j) in the given list, so that the concatenation of the two words words[i] + words[j] is a palindrome.
Example 1:
Input: words = ["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: words = ["bat","tab","cat"] Output: [[0,1],[1,0]] Explanation: The palindromes are ["battab","tabbat"]
Example 3:
Input: words = ["a",""] Output: [[0,1],[1,0]]
Constraints:
1 <= words.length <= 50000 <= words[i].length <= 300words[i]consists of lower-case English letters.
Accepted
166,128
Submissions
474,595
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
class Solution:
def palindromePairs(self, words: List[str]) -> List[List[int]]:
wd = {word[::-1]:i for i,word in enumerate(words)}
res = []
# for loop through words list
for idx, word in enumerate(words):
# for loop through each word
for i in range(len(word) + 1):
# make prefix, postfix
prefix, postfix = word[:i], word[i:]
# prefix + postfix (this should be palind) + prefix.reverse
if prefix in wd and idx!=wd[prefix] and postfix==postfix[::-1]:
res.append( [ idx, wd[prefix] ] )
# postfix + prefix + postfix.reverse
if i>0 and postfix in wd and idx!=wd[postfix] and prefix == prefix[::-1]:
res.append([wd[postfix],idx])
return res 
