JAVA "short" solution with fair speed, 33ms.


  • 1
    O

    This is not an optimized solution. However, I somehow want to keep it simple and short for the purpose of interview (providing a working solution within limited time). You may find that each function is simple. The "findAbb" generates an abbreviation and "hasSameAbb" check if this abbreviation has conflict with a word in the dictionary. The only optimizations are (1) when doing DFS, using number first so that the abbreviation length tried earlier is short and (2) when the length of current abbreviation is greater than the current shortest abbreviation, return.

    '''

    public String minAbbreviation(String target, String[] dictionary) {
        if (target == null) { return null; }
        if (target.length() == 0) { return ""; }
        int[] len = new int[1];
        len[0] = Integer.MAX_VALUE;
        String[] res = new String[1];
        res[0] = "";
        findAbb(target, "", 0, 0, 0, len, res, dictionary);
        return res[0];
    }
    
    public void findAbb(String target, String temp, int skip, int pos, int length, int[] len, String[] res, String[] dict) {
        int n = target.length();
        if (length >= len[0]) { return; }
        if (pos == n) {
            temp = skip == 0 ? temp : temp + skip;
            length = skip == 0 ? length : length + 1;
            if (hasSameAbb(temp, dict)) { return; }
            len[0] = length;
            res[0] = temp;
            return;
        }
        findAbb(target, temp, skip + 1, pos + 1, length, len, res, dict);
        findAbb(target, temp + (skip == 0 ? "" : skip) + target.charAt(pos), 0, pos + 1, skip == 0 ? length + 1 : length + 2, len, res, dict);
    }
    
    public boolean hasSameAbb(String temp, String[] dict) {
        int n = temp.length();
        for (String str : dict) {
            int i = 0, j = 0, len = str.length(), num = 0;
            boolean pass = false;
            for (; j < n; j++) {
                char c = temp.charAt(j);
                if (c >= '0' && c <= '9') {
                    num = num * 10 + c - '0';
                    continue;
                }
                i += num;
                num = 0;
                if (i >= len || str.charAt(i++) != c) {
                    pass = true;
                    break;
                }
            }
            if (pass) { continue; }
            i += num;
            if (i == len) { return true; }
        }
        return false;
    }
    

    '''


Log in to reply
 

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