[Java/C++] Clean Code


  • 13
    1. Sort the words alphabetically, therefore shorter words always comes before longer words;
    2. Along the sorted list, populate the words that can be built;
    3. Any prefix of a word must comes before that word.

    Java

    class Solution {
        public String longestWord(String[] words) {
            Arrays.sort(words);
            Set<String> built = new HashSet<String>();
            String res = "";
            for (String w : words) {
                if (w.length() == 1 || built.contains(w.substring(0, w.length() - 1))) {
                    res = w.length() > res.length() ? w : res;
                    built.add(w);
                }
            }
            return res;
        }
    }
    

    C++

    class Solution {
    public:
        string longestWord(vector<string>& words) {
            sort(words.begin(), words.end());
            unordered_set<string> built;
            string res;
            for (string w : words) {
                if (w.size() == 1 || built.count(w.substr(0, w.size() - 1))) {
                    res = w.size() > res.size() ? w : res;
                    built.insert(w);
                }
            }
            return res;
        }
    };
    

  • 0
    F

    Same idea

    class Solution {
        public String longestWord(String[] words) {
            Arrays.sort(words);
            Set<String> set = new HashSet<>();
            String res = "";
            for (String word: words) {
                if (word.length() == 1 || set.contains(word.substring(0, word.length() - 1))){
                    set.add(word);
                    if (word.length() > res.length()) {
                        res = word;
                    } 
                }
            }
            return res;
        }
    }
    

  • 0
    V

    Would be more space optimized if done using Trie. Here the space complexity is O(nk) where n is number of words in dict and k is average length of word, whereas the space required for Trie is O(nk) in worst case.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.