share my 25ms AC Java solution


  • 0
    C

    At first. I sort the dictionary to ensure that we check the words in the lexicographical order.
    During the check process, I use two pointer to judge whether the s contains the words in the dict. if s contains, we put the words of dict into the list
    Finally I go through the list to obtain the longest one with the smallest lexicographical order.

        public String findLongestWord(String s, List<String> d) {
            List<String> results = new ArrayList<>();
            Collections.sort(d);
            for (String str : d){
                if (str.length() > s.length()) continue;
                if (helper(s, str)) results.add(str);
            }
            int index = 0, max = Integer.MIN_VALUE;
            if (results.size() == 0) return "";
            for (int i = 0; i < results.size(); i++){
                int size = results.get(i).length();
                if (max < size){
                    max = size;
                    index = i;
                }
            }
            return results.get(index);
        }
        private boolean helper(String s, String d){
            int index = 0;
            for (int i = 0; i < d.length(); i++){
                char ch = d.charAt(i);
                int found = s.indexOf(ch, index);
                if (found != -1){
                    index = found + 1;
                } else {
                    return false;
                }
            }
            return true;
        }
    }

Log in to reply
 

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