My java AC solution using set and stack


  • 0
    L
    public String longestWord(String[] words) {
            
            Set<String> prefixes = new HashSet<>();
            LinkedList<String> stack = new LinkedList<>();
            
            Arrays.sort(words, new StrlenComparator());//sort the words
            
            int dic_len = words.length;//size of dictionary
            
            //add the word if the dictionary contains the prefix
            for(int i = 0; i < dic_len; ++i) {
                if (words[i].length() == 1) {
                    prefixes.add(words[i]);
                    stack.push(words[i]);
                    continue;
                }
                if (prefixes.contains(words[i].substring(0, words[i].length() - 1))){
                    prefixes.add(words[i]);
                    stack.push(words[i]);
                }
            }
            
            if(stack.isEmpty()) return null;
            
            //the longest prefix is the answer
            String p = stack.pop(), q;
            while ((q = stack.poll()) != null) {
                if (q.length() != p.length()) return p;
                else p = q;
            }
            if (p.length() == 1) return p;//consider the stack ['a''x''e']
            return null;
        }
        
        class StrlenComparator implements Comparator<String>{
            //length first then lexicographical order
            public int compare(String s1, String s2) {
                int k = s1.length() - s2.length();
                return (k == 0) ? s1.compareTo(s2) : k;
            }
        }
    

    This cost 38ms, hoping for your quicker answer!


Log in to reply
 

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