LeetCode Q320: 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:
I was totally confused when this question first come to me. I can't figure out what pattern is hidden behind example results.

However, if you can consider a string a bit array, then represent it using digit or characters is no difference than setting bit to 1 or 0.

So, for a given string with n characters, there are totally 2^n ways to represent it

When this is clear, we can easily solve it using backtracking. Although we could even use bit manipulation to speed up, due to time limitation, we use a vector instead.




Round 2 solution: