Write a function to generate the generalized abbreviations of a word.
Example:
Given word = "word", return the following list (order does not matter):
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]
一刷
題解：abbreviation, backtracking
class Solution {
public List<String> generateAbbreviations(String word) {
List<String> res = new ArrayList<>();
bt(res, word, 0, "", 0);
return res;
}
private void bt(List<String> res, String word, int pos, String cur, int count){
if(pos == word.length()){
if(count>0) cur+=count;
res.add(cur);
}
else{
bt(res, word, pos+1, cur, count+1);//abrevation the pos
if(count>0){
bt(res, word, pos+1, cur+count+word.charAt(pos), 0);
}else{
bt(res, word, pos+1, "" + word.charAt(pos), 0);
}
}
}
}
二刷
類似于DFS, 分清abbreviation和not abbreviation的情況
class Solution {
public List<String> generateAbbreviations(String word) {
List<String> res = new ArrayList<>();
//if(word == null || word.length()==0) return res;
bt(word, 0, res, 0, "");
return res;
}
private void bt(String word, int pos, List<String> res, int count, String cur){
//abbreviation or not
if(pos == word.length()){
if(count>0) res.add(cur + count);
else res.add(cur);
return;
}
//abbreviation
bt(word, pos+1, res, count+1, cur);
//not abbreviation
if(count != 0) bt(word, pos+1, res, 0, cur+count+word.charAt(pos));
else bt(word, pos+1, res, 0, cur+word.charAt(pos));
}
}
