# 0320. Generalized Abbreviation
###### tags: `Leetcode` `Bit Manipulation` `Medium` `BackTracking` `Bit Mask`
Link: https://leetcode.com/problems/generalized-abbreviation/
## 思路
### Bit Mask
我们遍历00..0到11..1的所有n位二进制状态。如果某位上是0，那么对应位置的字符就保留。如果某位上是1，那么对应位置上的字符就要被缩略
### BackTracking
由于对于每个字符来说只有两种选择 abbreviate和不abbreviate
涉及到这种abbreviation类型的backtracking一定要小心
因为不确定abbreviation的数字长度 所以不能像其他题目一样dfs之后直接把最后一个element删掉就可以了
而是需要在末尾加上```curr.setLength(len);```
## Code
### Bit Mask

class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> ans = new ArrayList<>();
        for(int i=0; i<(1<<word.length()); i++){
            ans.add(abbr(word, i));
        }
        return ans;
    }
    private String abbr(String word, int mask){
        StringBuilder sb = new StringBuilder();
        int cnt = 0;
        for(int i=0; i<word.length(); i++){
            if(((mask>>i)&1)==0){
                if(cnt!=0) sb.append(cnt);
                cnt = 0;
                sb.append(word.charAt(i));
            }
            else cnt++;
        }
        if(cnt!=0) sb.append(cnt);
        return sb.toString();
    }
}

### BackTracking

class Solution:
    def generateAbbreviations(self, word: str) -> List[str]:
        ans = []

        def backtracking(start, count, currStr):
            if start == len(word):
                currStr += str(count) if count>0 else ""
                ans.append(currStr[:])
            else:
                # stop adding count, keep current character
                backtracking(start+1, 0, currStr+(str(count) if count>0 else "")+word[start])

                # keep adding count
                backtracking(start+1, count+1, currStr)

        backtracking(0, 0, "")
        return ans

class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> ans = new ArrayList<>();
        dfs(ans, word, new StringBuilder(), 0, 0);
        return ans;
    }
    private void dfs(List<String> ans, String word, StringBuilder curr, int start, int count){
        int len = curr.length();
        if(start==word.length()){
            if(count!=0) curr.append(count);
            ans.add(curr.toString());
        }
        else{
            //abbreviation
            dfs(ans, word, curr, start+1, count+1);

            //no abbreviation
            if(count!=0){
                curr.append(count);
            }
            dfs(ans, word, curr.append(word.charAt(start)), start+1, 0);
        }
        curr.setLength(len);
    }
}