6ms fast java solution(beats 100%)


  • 3
    Q

    The idea is simple:

    1. for each character of the "word", we can either abbreviate it or not abbreviate it.

    2. if we abbreviate, we can abbreviate one character, or two characters,...,or all characters of the remaining string.

    3. if we abbreviate the first k characters, the k + 1 character must not be abbreviated; otherwise, we should abbreviate these k + 1
      characters rather than just the first k

    4. After each phase, deal with the remaining string using the same way

    5. parse the length of abbreviation number by yourself can be a little faster than using java lib.

    public List<String> generateAbbreviations(String word) {
        List<String> res = new ArrayList<String>();
        if (word.length() == 0) {
            res.add(word);
            return res;
        }
        char[] c = word.toCharArray();
        char[] aux = new char[word.length()]; //auxiliary array for generating abbreviation
        generateAbbreviations(aux, 0, c, 0, res);
        return res;  
    }
    private void generateAbbreviations(char[] aux, int p1, char[] c, int p2, List<String> res){
        // not abbr
        aux[p1] = c[p2];
        if (p2 == c.length - 1) res.add(new String(aux, 0, p1 + 1));
        else generateAbbreviations(aux, p1 + 1, c, p2 + 1, res);
        // abbr
        for (int i = 1; i <= c.length - p2; i++){
            int l = i;//length of abbreviation
            int p = p1;
            while(l >= 10){
                aux[p++] = (char)(l / 10 + '0');
                l = l - l / 10 * 10; 
            }
            aux[p++] = (char)(l + '0');
            if (p2 + i == c.length) res.add(new String(aux, 0, p)); // abbr all the remaining
            else if (p2 + i == c.length - 1) { // abbr all the remaining except the last character
                aux[p++] = c[p2 + i];// the following character cannot be abbreviated
                res.add(new String(aux, 0, p));
            }
            else {
                aux[p++] = c[p2 + i];// the following character cannot be abbreviated
                generateAbbreviations(aux, p, c, p2 + i + 1, res);
            }
        }
    }

  • 0
    Q
    This post is deleted!

  • 0
    Q

    a relatively concise solution but double the time

    public List<String> generateAbbreviations(String word) {
        List<String> res = new ArrayList<String>();
        char[] c = word.toCharArray();
        char[] aux = new char[word.length()]; //auxiliary array for generating abbreviation
        generateAbbreviations(aux, 0, c, 0, res);
        return res;  
    }
    private void generateAbbreviations(char[] aux, int p1, char[] c, int p2, List<String> res){
        if (p2 == c.length) {
            res.add(new String(aux, 0, p1));
            return;
        }
        // not abbr
        aux[p1] = c[p2];
        generateAbbreviations(aux, p1 + 1, c, p2 + 1, res);
        // abbr
        for (int i = 1; i <= c.length - p2; i++){
            int l = i;//length of abbreviation
            int p = p1;
            while(l >= 10){
                aux[p++] = (char)(l / 10 + '0');
                l = l % 10; 
            }
            aux[p++] = (char)(l + '0');
            if (p2 + i <= c.length - 1) {
                aux[p++] = c[p2 + i];// the following character cannot be abbreviated
                generateAbbreviations(aux, p, c, p2 + i + 1, res);
            }
            else generateAbbreviations(aux, p, c, p2 + i, res);
        }
    }

  • 0
    B

    Could you explain your code instead just cping and pasting? Thx.


  • 0
    Q

    added a brief explanation


Log in to reply
 

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