https://leetcode.com/problems/generalized-abbreviation/description/
这道题就是字母压缩成数字,还能多个位置压缩,但一定要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);
}