Short Java Solutions - Sorting Dictionary and Without Sorting


  • 35

    We sort the input dictionary by longest length and lexicography. Then, we iterate through the dictionary exactly once. In the process, the first dictionary word in the sorted dictionary which appears as a subsequence in the input string s must be the desired solution.

    public String findLongestWord(String s, List<String> d) {
        Collections.sort(d, (a,b) -> a.length() != b.length() ? -Integer.compare(a.length(), b.length()) :  a.compareTo(b));
        for (String dictWord : d) {
            int i = 0;
            for (char c : s.toCharArray()) 
                if (i < dictWord.length() && c == dictWord.charAt(i)) i++;
            if (i == dictWord.length()) return dictWord;
        }
        return "";
    }
    

    An alternate, more efficient solution which avoids sorting the dictionary:

    public String findLongestWord(String s, List<String> d) {
        String longest = "";
        for (String dictWord : d) {
            int i = 0;
            for (char c : s.toCharArray()) 
                if (i < dictWord.length() && c == dictWord.charAt(i)) i++;
    
            if (i == dictWord.length() && dictWord.length() >= longest.length()) 
                if (dictWord.length() > longest.length() || dictWord.compareTo(longest) < 0)
                    longest = dictWord;
        }
        return longest;
    }
    

    Time Complexity: O(nk), where n is the length of string s and k is the number of words in the dictionary.


  • 0

    Cool! Could you explain

    Collections.sort(d, (a,b) -> a.length() != b.length() ? -Integer.compare(a.length(), b.length()) :  a.compareTo(b));
    

    ? Thanks!!!


  • 3

    @BryanBo.Cao This line sorts the list of strings. The "(a,b) -> ..." is used to specify how the sorting method should compare any two strings in the list. If the lengths of the string are not equal, we want the string with the longer length to be first. If the strings are of equal length, then we want the lexicographically lesser string to appear first in the sorted list.


  • 0

    Good solution!@compton_scatter , I use back-track, but TLE, could you help me to see something wrong in my code. Thanks!

    public class Solution {
        String max;
        public String findLongestWord(String s, List<String> d) {
            max = "";
            backtrack(s, d, new StringBuilder(), 0);
            return max;
        }
        void backtrack(String s, List<String> d, StringBuilder sb, int start){
            if(d.contains(sb.toString())&&sb.length()>max.length()){
                max = sb.toString();
            }else if(d.contains(sb.toString())&&sb.length()==max.length()){
                max = max.compareTo(sb.toString())>0?(sb.toString()):max;
            }
            for(int i = start;i<s.length();i++){
                sb.append(s.charAt(i));
                backtrack(s, d, sb, i+1);
                sb = sb.deleteCharAt(sb.length()-1);
            }
        }
    }
    
    //the input 
    "aewfafwafjlwajflwajflwafj"
    ["apple","ewaf","awefawfwaf","awef","awefe","ewafeffewafewf"]
    

  • 0

    @LJerRRy
    The biggest difference of your code to the topic poster's code is you use the dictionary as the pattern and try to fit the string which can be very long (well, the word in the dictionary can also be very long. If the length of the words in the dictionary have the same length with String s, there should be no difference). But @compton_scatter uses the string as the pattern and try to fit the words in the dictionary. I think the test case may affect the result to some extent. And the sorted solution could be more reliable than the unsorted one.
    BTW, I also had the TLE problem here, I used Trie though.

    String max;
    public String findLongestWord(String s, List<String> d) {
        max = new String();;
        TrieNode root = new TrieNode();
        buildTrie(root,d);
        helper(s,0,root);
        return max;
    }
    
    private void helper(String s, int i, TrieNode curr){
        if(curr.word!=null){
            if(curr.word.length()>max.length()){
                max = curr.word;
            }
            else if(curr.word.length()==max.length()){
                if(curr.word.compareTo(max)<0){
                    max = curr.word;
                }
            }
        }
        if(i==s.length()||curr.maxlen<max.length()) return;
        char c = s.charAt(i);
        if(curr.children[c-'a']!=null){
            helper(s,i+1,curr.children[c-'a']);
        }
        helper(s,i+1,curr);
    }
    
    private void buildTrie(TrieNode root, List<String> d){
        for(String s: d){
            TrieNode curr = root;
            curr.maxlen = Math.max(curr.maxlen,s.length());
            for(int i = 0;i<s.length();i++){
                char c = s.charAt(i);
                if(curr.children[c-'a']==null){
                    curr.children[c-'a'] = new TrieNode();
                }
                curr = curr.children[c-'a'];
                curr.maxlen = Math.max(curr.maxlen,s.length());
            }
            curr.word = s;
        }
    }
    
    
    class TrieNode{
        String word;
        TrieNode[] children;
        int maxlen;//even adding this var, trying to make the search end earlier, still TLE.
        public TrieNode(){
            word = null;
            maxlen = 0;
            children = new TrieNode[26];
        }
    }

  • 0
    D

    Why is it more efficient to not sort the dictionary? Sorting allows you to break out of the search early, whereas the second solution must iterate through every entry in the dictionary once.


  • 0

    @david120

    I think it may be because the sort itself takes O(nlogn * m), where m is the average size of each string.


  • 1
    W

    I was asked this question during intern phone interview with Google, and gave the similar answer after a few optimization, but sadly the interviewer are not satisfied at all, he wants optimization to improve time complexity...


  • 0
    S

    compare() returns -1 if 1st argument<2nd argument and this is used for sorting integers in ascending order by default. To make it sort in descending order, we negate the returned value, to make the function return negative 1 when 1st arg>2nd arg, thereby sorting in descending order. If the length of two strings is equal, then we use the compareTo method of String object to sort in lexicographical order.


  • 4

    No sorting, go through the dictionary and check if any word is a subsequence of s.

        public String findLongestWord(String s, List<String> d) {
           String res = "";
           for(String w: d){
             if(isSubsequence(w, s)){
               if(w.length() > res.length()) res = w; 
               if(w.length() == res.length() && w.compareTo(res) < 0) res = w;  
             }  
           }    
           return res;
        }
        
        boolean isSubsequence(String w, String s){
          char[] wc = w.toCharArray();
          char[] sc = s.toCharArray();
          int i = 0, j = 0;
          while(i < wc.length && j < sc.length){
            if(wc[i] == sc[j]) i++;
            j++;    
          }  
          return i == wc.length;  
        }

Log in to reply
 

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