// 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();
}
}
