Comment on page

# 320.Generalized-Abbreviation

## 题目描述

Write a function to generate the generalized abbreviations of a word.
Note: The order of the output does not matter.
Example:
Input: "word"
Output:
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

## 代码

### Approach #1 Backtracking

Time: O(n 2^n) && Space: O(n)
class Solution {
public List<String> generateAbbreviations(String word) {
List<String> ans = new ArrayList<String>();
backtrack(ans, new StringBuilder(), word, 0, 0);
return ans;
}
private void backtrack(List<String> ans, StringBuilder builder, String word, int i, int k) {
int len = builder.length();
if (i == word.length()) {
if (k != 0) builder.append(k);
} else {
backtrack(ans, builder, word, i+1, k+1);
if (k != 0) builder.append(k);
builder.append(word.charAt(i));
backtrack(ans, builder, word, i+1, 0);
}
builder.setLength(len); // reset builder to the original state
}
}

### Approach #2 Bit Manipulation

Time: O(n 2^n) && Space: O(n)
class Solution {
public List<String> generateAbbreviations(String word) {
List<String> ans = new ArrayList<>();
for (int x = 0; x < (1 << word.length()); x++) {
}
return ans;
}
private String abbr(String word, int x) {
StringBuilder builder = new StringBuilder();
int count = 0;
for (int i = 0; i < word.length(); i++, x >>= 1) {
if ((x & 1) == 0) {
if (count != 0) {
builder.append(k);
count = 0;
}
builder.append(word.charAt(i));
} else {
count++;
}
}
if (k != 0) builder.append(count);
return builder.toString();
}
}