[LeetCode] Python - 720. Longest Word in Dictionary

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

Longest Word in Dictionary - LeetCode

 

 

한번에 한 문자를 만들수 있는 단어중에서 사전순으로 가장 작고, 가장 긴 단어를 찾는 문제이다.

 

생각

1. set으로 구성된 리스트를 만들고 처음은 빈 문자열로 초기화해준다. 조건에 해당하지 않는 경우 빈 문자열을 리턴해야하기 때문에 빈문자열을 원소로 가지게끔 초기화가 필요하다. (단어의 마지막 한글자를 빼고 체크하기 때문에도 필요함)

2. 짧은 단어부터 시작하여 긴 단어에 해당하는지 확인해야하기때문에, 주어진 words를 길이 순으로 정렬한다. 

3. 마지막 한글자를 제외한 단어가 set배열에 있다면 set배열에 단어를 추가한다

4. res를 길이순으로 정렬하고 가장 긴 단어를 반환한다. 

 

Python Code

class Solution(object):
    def longestWord(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        res = set([""])
        words.sort(key=lambda x : len(x))
        for word in words:
            if word[:-1] in res:
                res.add(word)
        
        return max(sorted(res), key=lambda x:len(x))