### 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.

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 IListGenerateAbbreviations(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; } }

## Comments

## Post a Comment