Tuesday, October 11, 2016

Generalized Abbreviation


Question:
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"]

This is definitely backtracking. However, it's not as straightforward as I thought. The termination part is clear: when we reach the end of the string. For the recursion part, we know for each word, either it is abbreviated, or it's added to the result string. For the first case, we increment the count and recursively get the result string. For the second case, if the count is already greater than 0, before appending the char, we need to append the count first, then reset count to 0 for recursion after we append the char.


public List<string> generateAbbreviations(String word) {
        List<string> rst = new ArrayList<>();
        if (word.length() == 0) {
            return rst;
        }
        getWords(word, rst, new StringBuilder(), 0, 0);
        return rst;
    }

    private void getWords(String word, List<string> rst, StringBuilder curr, int pos, int count) {
        int len = curr.length();
        if (pos == word.length()) {
            if (count > 0) {
                curr.append(count);
            }
            rst.add(curr.toString());
        } else {
            getWords(word, rst, curr, pos + 1, count + 1);
            if (count > 0) {
                curr.append(count);
            }
            curr.append(word.charAt(pos));
            getWords(word, rst, curr, pos + 1, 0);
        }
        curr.setLength(len);
    }


No comments:

Post a Comment