# 320.Generalized-Abbreviation

## ้ข็ฎๅฐๅ

https://leetcode.com/problems/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();
}
}``````

Last updated