엔지니어 게시판
LeetCode 솔루션 분류

[9/17] 336. Palindrome Pairs

컨텐츠 정보

본문

Hard
3471345Add to ListShare

Given 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 <= 5000
  • 0 <= words[i].length <= 300
  • words[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  
전체 396 / 6 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 155 명
  • 오늘 방문자 1,480 명
  • 어제 방문자 6,462 명
  • 최대 방문자 11,134 명
  • 전체 회원수 1,049 명
알림 0