[파이썬 알고리즘 인터뷰][트라이] 팰린드롬 페어

[파이썬 알고리즘 인터뷰][트라이] 팰린드롬 페어

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다.

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

문제 정의

리스트에 포함된 두 문자열이 더해져서 팰린드롬이 되는 문자열의 인덱스 pair들 출력

책에서 구현된 코드

import collections from typing import List # 트라이 저장할 노드 class TrieNode: def __init__(self): self.children = collections.defaultdict(TrieNode) self.word_id = -1 self.palindrome_word_ids = [] class Trie: def __init__(self): self.root = TrieNode() @staticmethod def is_palindrome(word: str) -> bool: return word[::] == word[::-1] # 단어 삽입 def insert(self, index, word) -> None: node = self.root for i, char in enumerate(reversed(word)): if self.is_palindrome(word[0:len(word) - i]): node.palindrome_word_ids.append(index) node = node.children[char] node.word_id = index def search(self, index, word) -> List[List[int]]: result = [] node = self.root while word: # 판별 로직 3) (본문 설명 참고) if node.word_id >= 0: if self.is_palindrome(word): result.append([index, node.word_id]) if not word[0] in node.children: return result node = node.children[word[0]] word = word[1:] # 판별 로직 1) (본문 설명 참고) if node.word_id >= 0 and node.word_id != index: result.append([index, node.word_id]) # 판별 로직 2) (본문 설명 참고) for palindrome_word_id in node.palindrome_word_ids: result.append([index, palindrome_word_id]) return result class Solution: def palindromePairs(self, words: List[str]) -> List[List[int]]: trie = Trie() for i, word in enumerate(words): trie.insert(i, word) results = [] for i, word in enumerate(words): results.extend(trie.search(i, word)) return results

기억해야할 기법

어려운 문제일수록 자료구조를 만들어서 단순화하자

내가 구현한 코드

from typing import List class TrieNode: def __init__(self, val: str = "", depth: int = -1, idx: int = -1): self.val = val self.idx = idx self.depth = depth self.child = dict() class Trie: def __init__(self): self.trie = TrieNode() def insert(self, word: list[str], i: int) -> None: crnt = self.trie for d, c in enumerate(word): if c not in crnt.child: crnt.child[c] = TrieNode(c,d) crnt = crnt.child[c] crnt.idx = i def is_palindrome(self, word:str) -> bool: return word == word[::-1] def get_palindrome(self, words: str, searcher: int) -> List[int]: def dfs(crnt: TrieNode, apnd: str): result = [] # 1. 단어 완성 2. 검색 대상과 다름 3. 펠린드롬 만족 if crnt.idx != -1 and crnt.idx != searcher and self.is_palindrome(words+apnd): result.append(crnt.idx) for k, node in crnt.child.items(): # 검색 대상과 펠린드롬이 불가능하다면 continue if node.depth < len(words) and node.val != words[node.depth]: continue result += dfs(node, k+apnd) return result return dfs(self.trie, "") class Solution: def palindromePairs(self, words: List[str]) -> List[List[int]]: trie = Trie() result = [] for i, word in enumerate(words): trie.insert(list(word)[::-1], i) for i, word in enumerate(words): for j in trie.get_palindrome(word, i): if i != j: result.append([i,j]) return result

구현한 로직에 대한 예외상황이 중첩되었다

풀이를 떠올려도 구현이 안되는 너무 어려운 문제였다

속도 차이가 크다

- 책에서 구현한 알고리즘의 속도가 2.3초 정도인데, 내가 구현한 알고리즘은 3.1초다

- 책에서 구현한 알고리즘의 속도가 2.3초 정도인데, 내가 구현한 알고리즘은 3.1초다 트라이 활용하는 문제를 더 풀어봐야겠다

from http://pythaac.tistory.com/132 by ccl(A) rewrite - 2021-08-05 19:00:16