Abbreviation non-recursive: reusing technique for subsets generation

A while back I posted a nice non-recursive trick for subsets generation involving bits manipulation, right here A non-recursive trick for subsets generation (dreaktor.com). The problem today reuses that trick. The idea is the following:

1/ Think about the same process to generate the subsets as described in the link above

2/ If the bit is one, increment the counter

3/ If the bit is zero, check if we have a counter to append, reset the counter, and append the current character

4/ Make sure to do one more check for the counter after exiting the inner loop

Complexity will be O(N * 2*N), and since N = 15, we're talking about ~500K iterations (plus the cost of the string manipulation), which is passable. Code is down below, cheers, ACC.

Generalized Abbreviation - LeetCode

320. Generalized Abbreviation

Medium

A word's generalized abbreviation can be constructed by taking any number of non-overlapping substrings and replacing them with their respective lengths. For example, "abcde" can be abbreviated into "a3e" ("bcd" turned into "3"), "1bcd1" ("a" and "e" both turned into "1"), and "23" ("ab" turned into "2" and "cde" turned into "3").

Given a string word, return a list of all the possible generalized abbreviations of word. Return the answer in any order.

 

Example 1:

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

Example 2:

Input: word = "a"
Output: ["1","a"]

 

Constraints:

• 1 <= word.length <= 15
• word consists of only lowercase English letters.

Accepted

57,068

Submissions

103,256

public class Solution {
    public IList GenerateAbbreviations(string word)
    {
        List retVal = new List();

        for (int i = 0; i < (int)Math.Pow(2, word.Length); i++)
        {
            string str = "";
            int n = i;
            int count = 0;
            for (int j = 0; j < word.Length; j++)
            {
                if (n % 2 == 0)
                {
                    if (count > 0) str += count.ToString();
                    count = 0;
                    str += word[j].ToString();
                }
                else
                {
                    count++;
                }
                n /= 2;
            }
            if (count > 0) str += count.ToString();
            retVal.Add(str);
        }

        return retVal;
    }
}