320. Generalized Abbreviation

LeetCode 320. Generalized Abbreviation

Description

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.

Tags

Bit Manipulation

Solution

We can observe that the result is sort of related to bits representation (since the length of output is 2^n, n = len(word)). Thus, we iterate a bit-mask variable from 0 to 2^n-1. (e.g. for word = "word", we iterate from 0000 to 1111), and rules to generate a word are:

• we initialize a counter variable to count continuous 1, as well as a byte slice w whose capacity is n;

• we check bits of the current bit-mask one by one with the pointer j:

  • if the bit bitmask[j] is 1, increase the counter by 1;

  • if the bit bitmask[j] is 0, convert the counter type from integer to string only if the counter is greater than 0, and concatenate w to it, then clear the counter. Also, append word[j] to w.

• convert the counter type from integer to string only if the counter is greater than 0, and concatenate w to it.

• convert the type of w from []byte to string, and append it to the result slice.

Complexity

• Time complexity: $O(n2^n)$

• Space complexity: $O(n)$

Code

func generateAbbreviations(word string) []string {
	bitmask := int(math.Pow(2, float64(len(word)))) - 1
	ans := make([]string, bitmask+1)
	for i := 0; i <= bitmask; i++ {
		count, w := 0, make([]byte, 0, len(word))
		for j := 0; j < len(word); j++ {
			if b := i >> j; b&1 == 1 {
				count++
			} else if b&1 == 0 {
				if count != 0 {
					w = append(w, []byte(strconv.Itoa(count))...)
					count = 0
				}
				w = append(w, word[j])
			}
		}
		if count != 0 {
			w = append(w, []byte(strconv.Itoa(count))...)
		}
		ans[i] = string(w)
	}
	return ans
}