[1스4코2파] # 212 LeetCode 720. Longest Word in Dictionary

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (212차)
[4코1파] 2023.01.13~ (204일차)
[1스4코1파] 2023.04.12~ (115일차)
[1스4코2파] 2023.05.03 ~ (93일차)

Today :

2023.08.04 [212일차]
Prefix Tree(Trie)
105. Construct Binary Tree from Preorder and Inorder Traversal

720. Longest Word in Dictionary

https://leetcode.com/problems/longest-word-in-dictionary/description/

문제 설명

주어진 words 배열에서, 가장 긴 문자열을 return 함
이때 문자열 길이가 같을 경우 사전 순서에서 더 앞에ㅏ 있는 글자를 return 하면 되겠습니다.

문제 풀이 방법

TreeNode 클래스로 하나 만들고,
Trie 클래스로 하나 만들어서
bfs로 search 해서 찾았음
팁은 주어진 words를 sort한 다음 search를 시작하는 것이다.

내 코드

class TreeNode:
    def __init__(self):
        self.children = {}
        self.isWord = False
        self.val = ''

class Trie:
    def __init__(self):
        self.root = TreeNode()

    def addWord(self, word):
        cur = self.root
        for w in word:
            if w not in cur.children:
                cur.children[w] = TreeNode()
            cur = cur.children[w]
        cur.isWord = True
        cur.val = word

    def bfs(self):
        queue = [self.root]
        res = ''
        while queue:
            node = queue.pop(0)
            for child in node.children.values():
                if child.isWord :
                    queue.append(child)
                    if len(child.val) > len(res):
                        res = child.val

        return res


class Solution:
    def longestWord(self, words: List[str]) -> str:

        words.sort()
        root = Trie()
        for w in words:
            root.addWord(w)

        return root.bfs()

증빙

여담

sort 꿀팁 ㄳ