https://leetcode.com/problems/generalized-abbreviation/description/
image.png
这道题就是字母压缩成数字，还能多个位置压缩，但一定要2个数字中间至少隔一个字母。
所以我们可以想，每一个字母来，我们都可以选择压缩或不压缩。如果压缩，我们在原字符串上不动，但是维护一个CNT变量，代表连续的多少个字母被压缩了。如果不压缩，我们就把之前的CNT释放掉，随后加上这个字母。这样就可以保证，不会2个CNT连续释放的问题。
下面是代码
List<String> res = new ArrayList<>();
public List<String> generateAbbreviations(String word) {
help(word,0,0,"");
return res;
}
private void help(String word,int idx,int cnt,String cur) {
if(idx == word.length()){
res.add(cur+(cnt==0?"":cnt));
return ;
}
help(word,idx+1,0,cur+(cnt==0?"":cnt)+word.charAt(idx));
help(word,idx+1,cnt+1,cur);
}
follow up : 如果允许多重压缩呢，比如word可以压缩成22，或者13，或者1111.
那么我们就思考如何破除，cnt连续限制。
其实就是多加一个可能性，释放后接CNT，原先只有不释放接CNT。
释放后接CNT就是，cnt加到文字上，新的字母不跟在后面。
代码就加一行
List<String> res = new ArrayList<>();
public List<String> generateAbbreviations(String word) {
help(word,0,0,"");
return res;
}
private void help(String word,int idx,int cnt,String cur) {
if(idx == word.length()){
res.add(cur+(cnt==0?"":cnt));
return ;
}
help(word,idx+1,0,cur+(cnt==0?"":cnt)+word.charAt(idx));
if(cnt>0)
help(word,idx+1,1,cur+cnt);
help(word,idx+1,cnt+1,cur);
}
