320. Generalized Abbreviation

ref this:

https://www.cnblogs.com/grandyang/p/5261569.html

0000 word
0001 wor1
0010 wo1d
0011 wo2
0100 w1rd
0101 w1r1
0110 w2d
0111 w3
1000 1ord
1001 1or1
1010 1o1d
1011 1o2
1100 2rd
1101 2r1
1110 3d
1111 4

那么我们就可以观察出规律，凡是0的地方都是原来的字母，单独的1还是1，
如果是若干个1连在一起的话，就要求出1的个数，用这个数字来替换对应的字母

or 1 代表字母, 0 代表數字, 也可以

T: O(n*2^n),

S: O(2^n + n), n is string use

// T: O(n*2^n), S: O(2^n + n), n is string use
class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> ret = new ArrayList<>();
        int n = word.length();
        
        // mask from 0 ~ n^2, （run mask from 0000 to 1111
        // so if n = word.length() = 4 => 0~15, 
        // 4 位的 binary mask: 0000~1111
        for (int mask = 0; mask < (1 << n); mask++) { 
            ret.add(getAbbrev(word, mask));
        }
        return ret;
    }
    
    private String getAbbrev(String word, int mask) {
        StringBuilder abbrev = new StringBuilder();
        int n = word.length();
        
        for (int i = 0; i < n; i++) { // one by one, char convert to char or number 
            // 1 代表原本的文字, mask>>i 右移 i 位時, 是否為 1
            if ( ((mask>>i)&1) == 1) { 
                abbrev.append(word.charAt(i));  // append char
            } else {
                // 如果是若干个 0 连在一起的话，就要求出1的个数，用这个数字
                int j = i;
                // so use while
                while (j < n && ((mask>>j)&1) == 0) { // 0 代表縮寫數字, 計算個數
                    j++;
                }
                abbrev.append(j-i); // append number
                i = j-1;
            }
        }
        return abbrev.toString();
    }
}