Generalized Abbreviation

medium backtracking string bitmask

Problem

Return all generalized abbreviations of a word, where any subset of characters is replaced by a number equal to that subset's length.

Inputword = "word"

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

Each character is either kept literally or grouped into the running run-length.

word

def generate_abbreviations(word):
    res = []
    def back(i, cur, count):
        if i == len(word):
            res.append(cur + (str(count) if count else ""))
            return
        back(i + 1, cur, count + 1)
        back(i + 1, cur + (str(count) if count else "") + word[i], 0)
    back(0, "", 0)
    return res

function generateAbbreviations(word) {
  const res = [];
  function back(i, cur, count) {
    if (i === word.length) {
      res.push(cur + (count ? String(count) : ""));
      return;
    }
    back(i + 1, cur, count + 1);
    back(i + 1, cur + (count ? String(count) : "") + word[i], 0);
  }
  back(0, "", 0);
  return res;
}

class Solution {
    List res = new ArrayList<>();
    public List generateAbbreviations(String word) {
        back(word, 0, new StringBuilder(), 0); return res;
    }
    void back(String w, int i, StringBuilder cur, int count) {
        int len = cur.length();
        if (i == w.length()) {
            if (count > 0) cur.append(count);
            res.add(cur.toString());
        } else {
            back(w, i + 1, cur, count + 1);
            if (count > 0) cur.append(count);
            cur.append(w.charAt(i));
            back(w, i + 1, cur, 0);
        }
        cur.setLength(len);
    }
}

class Solution {
    vector res;
    void back(const string& w, int i, string cur, int count) {
        if (i == (int)w.size()) { res.push_back(cur + (count ? to_string(count) : "")); return; }
        back(w, i + 1, cur, count + 1);
        back(w, i + 1, cur + (count ? to_string(count) : "") + w[i], 0);
    }
public:
    vector generateAbbreviations(string word) { back(word, 0, "", 0); return res; }
};

Explanation

An abbreviation replaces some run of letters with a number giving that run's length. At each character we have exactly two choices: hide it (count it toward the current number) or keep it as a literal letter. Trying both choices everywhere produces every abbreviation.

The recursion back(i, cur, count) carries the abbreviation built so far (cur) and the length of the run of hidden letters we're currently accumulating (count). The two recursive calls are the two choices.

The hide branch is back(i + 1, cur, count + 1): we don't write anything yet, we just grow the count. The keep branch is back(i + 1, cur + (count or "") + word[i], 0): before writing the literal letter, we flush any pending count as a number, then reset count to 0.

When i reaches the end of the word, we flush any leftover count and record cur. Flushing only non-zero counts means we never write a stray 0.

Example: for "word", always-keep gives "word"; hiding the last letter gives "wor1"; hiding everything gives "4". All 2⁴ = 16 combinations come out this way.

Time: O(2^n) Space: O(2^n)