Java Sorting + HashMap O(nlogn + nL) Solution (Currently beats 95% of solution)


  • 0
    R

    The algorithm is divided into 3 parts.

    1. We sort the dictionary based on 3 criterias in the following order
      1.1 The last character
      1.2 The length
      1.2 Alphabetical

    2. The call the recursive function abbreviate, which checks that 2 or more words are of the same length and have the same leading character at index (letterIndex) and ending character. If so then there is a conflict, and we need to call abbreviate on the next character in the string and compare all the strings in conflict.
      Otherwise they do not conflict and we can "shrink"(abbreviation process) them.

    3. We put the abbreviated string in a map that maps the original string to the proper abbreviation. This is so we can iterate through the original dictionary and match the abbreviation for the original ordering constraint.

    List<String> sortedDict;
    Map<String, String> abbreviations;
    
    public List<String> wordsAbbreviation(List<String> dict) {
        abbreviations = new HashMap<>();
    
        sortedDict = new ArrayList<>(dict);
        Collections.sort(sortedDict, new Comparator<String>() {
    
            @Override
            public int compare(String o1, String o2) {
    
                int comp = o1.charAt(o1.length() - 1) - o2.charAt(o2.length() - 1);
                if (comp == 0) {
    
                    if (o1.length() < o2.length()) return -1;
                    else if (o1.length() > o2.length()) return 1;
                    else return o1.compareTo(o2);
                } else {
                    return comp;
                }
            }
        });
    
        abbreviate(0, sortedDict.size(), 0);
    
        return collect(dict, abbreviations);
    }
    
    private List<String> collect(List<String> dict, Map<String, String> abbreviations) {
        List<String> solution = new ArrayList<>();
    
        for (String word : dict) {
            solution.add(abbreviations.get(word));
        }
    
        return solution;
    }
    
    private String shrink(String word, int letterIndex) {
        if (word.length() - letterIndex < 4) return word;
    
        return word.substring(0, letterIndex + 1) + (word.length() - letterIndex - 2) + word.charAt(word.length() - 1);
    }
    
    private void abbreviate(int beg, int end, int letterIndex) {
    
        for (int i = beg; i < end; i++) {
            String word = sortedDict.get(i);
            int j = i + 1;
            while (j < end && word.length() == sortedDict.get(j).length()
                    && word.charAt(letterIndex) == sortedDict.get(j).charAt(letterIndex)
                    && word.charAt(word.length() - 1) == sortedDict.get(j).charAt(sortedDict.get(j).length() - 1)) {
                j++;
            }
            if (j > i + 1) {
                abbreviate(i, j, letterIndex + 1);
                i = j - 1;
            } else {
                abbreviations.put(word, shrink(word, letterIndex));
            }
        }
    }
    

Log in to reply
 

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