Welcome to Subscribe On Youtube

320. Generalized Abbreviation

Description

A word's generalized abbreviation can be constructed by taking any number of non-overlapping and non-adjacent 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")
  • "5" ("abcde" turned into "5")
  • "abcde" (no substrings replaced)
• However, these abbreviations are invalid:
  • "23" ("ab" turned into "2" and "cde" turned into "3") is invalid as the substrings chosen are adjacent.
  • "22de" ("ab" turned into "2" and "bc" turned into "2") is invalid as the substring chosen overlap.

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.

Solutions

Solution 1: DFS

We design a function $dfs(i)$, which returns all possible abbreviations for the string $word[i:]$.

The execution logic of the function $dfs(i)$ is as follows:

If $i \geq n$, it means that the string $word$ has been processed, and we directly return a list composed of an empty string.

Otherwise, we can choose to keep $word[i]$, and then add $word[i]$ to the front of each string in the list returned by $dfs(i + 1)$, and add the obtained result to the answer.

We can also choose to delete $word[i]$ and some characters after it. Suppose we delete $word[i..j)$, then the $j$ th character is not deleted, and then add $j - i$ to the front of each string in the list returned by $dfs(j + 1)$, and add the obtained result to the answer.

Finally, we call $dfs(0)$ in the main function.

The time complexity is $O(n \times 2^n)$, and the space complexity is $O(n)$. Where $n$ is the length of the string $word$.

Solution 2: Binary Enumeration

Since the length of the string $word$ does not exceed $15$, we can use the method of binary enumeration to enumerate all abbreviations. We use a binary number $i$ of length $n$ to represent an abbreviation, where $0$ represents keeping the corresponding character, and $1$ represents deleting the corresponding character. We enumerate all $i$ in the range of $[0, 2^n)$, convert it into the corresponding abbreviation, and add it to the answer list.

The time complexity is $O(n \times 2^n)$, and the space complexity is $O(n)$. Where $n$ is the length of the string $word$.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public List<String> generateAbbreviations(String word) {
          int n = word.length();
          List<String> ans = new ArrayList<>();
          for (int i = 0; i < 1 << n; ++i) {
              StringBuilder s = new StringBuilder();
              int cnt = 0;
              for (int j = 0; j < n; ++j) {
                  if ((i >> j & 1) == 1) {
                      ++cnt;
                  } else {
                      if (cnt > 0) {
                          s.append(cnt);
                          cnt = 0;
                      }
                      s.append(word.charAt(j));
                  }
              }
              if (cnt > 0) {
                  s.append(cnt);
              }
              ans.add(s.toString());
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      vector<string> generateAbbreviations(string word) {
          int n = word.size();
          vector<string> ans;
          for (int i = 0; i < 1 << n; ++i) {
              string s;
              int cnt = 0;
              for (int j = 0; j < n; ++j) {
                  if (i >> j & 1) {
                      ++cnt;
                  } else {
                      if (cnt) {
                          s += to_string(cnt);
                          cnt = 0;
                      }
                      s.push_back(word[j]);
                  }
              }
              if (cnt) {
                  s += to_string(cnt);
              }
              ans.push_back(s);
          }
          return ans;
      }
  };
  

• class Solution:
      def generateAbbreviations(self, word: str) -> List[str]:
          n = len(word)
          ans = []
          for i in range(1 << n):
              cnt = 0
              s = []
              for j in range(n):
                  if i >> j & 1:
                      cnt += 1
                  else:
                      if cnt:
                          s.append(str(cnt))
                          cnt = 0
                      s.append(word[j])
              if cnt:
                  s.append(str(cnt))
              ans.append("".join(s))
          return ans
  
  

• func generateAbbreviations(word string) (ans []string) {
  	n := len(word)
  	for i := 0; i < 1<<n; i++ {
  		s := &strings.Builder{}
  		cnt := 0
  		for j := 0; j < n; j++ {
  			if i>>j&1 == 1 {
  				cnt++
  			} else {
  				if cnt > 0 {
  					s.WriteString(strconv.Itoa(cnt))
  					cnt = 0
  				}
  				s.WriteByte(word[j])
  			}
  		}
  		if cnt > 0 {
  			s.WriteString(strconv.Itoa(cnt))
  		}
  		ans = append(ans, s.String())
  	}
  	return
  }
  

• function generateAbbreviations(word: string): string[] {
      const n = word.length;
      const ans: string[] = [];
      for (let i = 0; i < 1 << n; ++i) {
          const s: string[] = [];
          let cnt = 0;
          for (let j = 0; j < n; ++j) {
              if ((i >> j) & 1) {
                  ++cnt;
              } else {
                  if (cnt > 0) {
                      s.push(cnt.toString());
                      cnt = 0;
                  }
                  s.push(word[j]);
              }
          }
          if (cnt > 0) {
              s.push(cnt.toString());
          }
          ans.push(s.join(''));
      }
      return ans;
  }
  
  

All Problems

All Solutions