320 Generalized Abbreviation
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"]
分析& 代码
这道题没有做出来不应该。
显然是backtracking.
分两种情况：
一种是到当前位置的字母重新开始计数
一种是继续前一个字母的计数
需要注意的是，如果cnt==0是不要加到结果String里的
public List<String> generateAbbreviations(String word) {
List<String> res = new ArrayList<String>();
if(word == null) {
return res;
}
generate(res, word, 0, "", 0);
return res;
}
private void generate(List<String> res, String word, int index, String cur, int cnt) {
if(index == word.length()) {
res.add(cur + ((cnt == 0)?"":cnt));
return;
}
generate(res, word, index + 1, cur, cnt + 1);
generate(res, word, index + 1, cur + ((cnt == 0)?"":cnt) + word.charAt(index) , 0);
}