[LeetCode] Longest Word in Dictionary

문제 링크 >> https://leetcode.com/problems/longest-word-in-dictionary/

 

 

📋 문제

Given an array of strings words representing an English Dictionary, return the longest word in words that can be built one character at a time by other words in words.

If there is more than one possible answer, return the longest word with the smallest lexicographical order. If there is no answer, return the empty string.

 

 

👉 입출력

Example 1:

Input: words = ["w","wo","wor","worl","world"]
Output: "world"
Explanation: The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

Example 2:

Input: words = ["a","banana","app","appl","ap","apply","apple"]
Output: "apple"
Explanation: Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".

 

 

📝 풀이

class Solution:
    def longestWord(self, words: List[str]) -> str:
        arr = []
        result = ""
  
        for word in sorted(words):
            if word[:-1] in arr or len(word) == 1:
                arr.append(word)
                if len(result) < len(word):
                    result = word

        return result

 

주어진 단어들을 순회하면서 단어의 길이가 1인 것부터 먼저 arr에 저장한다.

그리고 단어의 길이가 2 이상인 것들은 끝의 문자를 잘라보고 자른 결과물이 arr에 있는지 확인한다.

arr에 있다면 이중 제일 긴 것들을 result에 저장하면서 result의 값을 갱신해 나간다.

 

원래 딕셔너리를 이용해 풀다가 value값으로 줄 것이 없는데 딕셔너리로 풀어야 하나 싶어서 리스트로 풀어보았다.

근데 풀고나니 리스트보다 set을 이용했으면 어땠을까 싶어서 set을 이용해봤더니 런타임에서 차이가 좀 나더라.

리스트를 이용해 풀었을 때는 156ms, set을 이용해 풀었을 때는 86ms였다.