Two Sets, no sorting and trie, 24ms beat 92%


  • 0
    class Solution {
        public String longestWord(String[] words) {
            String result = "";
            Set<String> set = new HashSet<>();
            for (int i = 0; i < words.length; i++) {
                set.add(words[i]);
            }
            Set<String> validSet = new HashSet<>(); // use this set to store the visited valid string, to avoid redundant validation
            for (String str: set) {
                if (str.length() > result.length() || (str.length() == result.length() && str.compareTo(result) < 0)) {
                    int len = str.length();
                    boolean valid = true;
                    while (len > 0) {
                        String temp = str.substring(0, len);
                        if (validSet.contains(temp)) {
                            break;
                        } 
                        if (!set.contains(temp)) {
                            valid = false;
                            break;
                        }
                        len--;
                    }
                    if (valid) {
                        validSet.add(str);
                        result = str;
                    }
                }
            }
            
            return result;
        }
    }
    

Log in to reply
 

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