首页 > itarticle > algorithm notes: leetcode#720 longest word in dictionary

algorithm notes: leetcode#720 longest word in dictionary

admin 11月 12, 2020 0

Problem

Solution

Analysis

Python implementation

class :
    def longestWord(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        valid = set([''])
        for word in sorted(words):
            if word[:-1] in valid:
                valid.add(word)
        return max(sorted(valid), key=len)

Java implementation

class  {
    public String longestWord(String[] words) {
        Set<String> valid = new HashSet<>();
        Arrays.sort(words);
        for(String word : words){
            if(word.length()<2 || valid.contains(word.substring(0, word.length()-1))){
                valid.add(word);
            }
        }
        String[] validArr = new String[valid.size()];
        validArr = valid.toArray(validArr);
        Arrays.sort(validArr);
        int maxLen = 0;
        for(String word : validArr){
            int curLen = word.length();
            maxLen = curLen > maxLen ? curLen : maxLen;
        }
        for(String word : validArr){
            System.out.println(word);
            if(word.length()==maxLen){
                return word;
            }
        }
        return "";
    }
}

Time complexity

O(nlogn).

Space complexity

O(n).

Link

720. Longest Word in Dictionary
(中文版) 算法笔记: 力扣#720 词典中最长的单词