320. Generalized Abbreviation

Write a function to generate the generalized abbreviations of a word.

Example:

Given word ="word", return the following list (order does not matter):

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

Solution:

Cut the word into left and right parts. The cutting point is from 0 to word.length(). For each cutting, construct the abbreviation by numberOfChars + charAtCutting + RecursiveRightPart. Two numbers cannot be neighbors.

    public List<String> generateAbbreviations(String word) {
        List<String> res = new ArrayList<String>();
        if (word.length() == 0) {
            res.add("");
            return res;
        }
        res.add("" + word.length());
        for (int i = 0; i < word.length(); i++) {
            String left = i > 0 ? "" + i : "";
            List<String> right = generateAbbreviations(word.substring(i + 1));
            for (String r : right) {
                res.add(left + word.charAt(i) + r);
            }
        }
        return res;
    }