31ms (beat 100% Java solutions). No Trie/HashMap/HashSet/Recursive. using sorting


  • 0
    T

    This solution beat 100% other Java solutions. It sorts modified words and then checks LCP (longest common prefix) between adjacent words. No trie/hashmap/hashset/recursive.

    First of all, how to sort the words? According to the description of the question, words with different lengths can be abbreviated to the same first and last letters, for example: "abbbc", and "abbbbc" => "a3c", "a4c". So, we sort words by length first. If 2 words have the same length, we compare them by signature of the words. A signature of a word is obtained by prefixing the word with the last letter. For example: "abc" => "cabc", "dog" => "gdog".

    The whole point of sorting is to make words with the same last letter + LCP grouped together.

    Now, for each word, we just need to compare it with the word right before it and the word right after it. Make sure the abbreviation generated are not conflicted with the abbreviations of these 2 words - without worry about all others.

    In general, each word has one LCP with the word right before it, and one LCP with the word right after it. To avoid conflicts, we should use the longer one of the these 2 LCPs to generate abbreviation.

    A few notes about the code:

    • a class called Word is used to keep original sequence after sorting
    • for words with different lengths, we sort them in descending order, that is words with longer lengths are put before words with shorter length
    • an empty string is added to the end to make corner case check easier.
        class Word implements Comparable<Word> {
            String wd;
            int idx;
    
            Word(String word, int idx) {
                this.wd = word;
                this.idx = idx;
            }
    
            public int compareTo(Word w) {
                if (this.wd.length() == w.wd.length())
                    return this.wd.compareTo(w.wd);
                return w.wd.length() - this.wd.length();
            }
        }
    
        public List<String> wordsAbbreviation(List<String> dict) {
            int n = dict.size();
            Word[] words = new Word[n + 1];
            for (int i = 0; i < n; i++) {
                String word = dict.get(i);
                words[i] = new Word(word.charAt(word.length() - 1) + word, i);
            }
            words[n] = new Word("", n);
    
            Arrays.sort(words);
    
            int pre = 0, cur = 0;
            for (int i = 0; i < n; i++) {
                String w1 = words[i].wd, w2 = words[i + 1].wd;
                cur = 0;
                if (w1.length() == w2.length()) {
                    cur = commonPrefix(w1, w2);
                }
                String abbr = getAbbr(w1, Math.max(cur, pre));
                dict.set(words[i].idx, abbr.length() < w1.length() - 1 ? abbr : w1.substring(1));
                pre = cur;
            }
    
            return dict;
        }
    
        private String getAbbr(String str, int prefLen) {
            if (prefLen == 0) prefLen = 1;
    
            int shortcut = str.length() - prefLen - 2;
            return str.substring(1, prefLen + 1) + shortcut + str.charAt(0);
        }
    
        private int commonPrefix(String s1, String s2) {
            int pref = 0;
            while (pref < s1.length()) {
                if (s1.charAt(pref) != s2.charAt(pref))
                    return pref;
                pref++;
            }
            return pref;
        }
    

Log in to reply
 

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