首页 > 代码库 > 320. Generalized Abbreviation

320. Generalized Abbreviation

这道题没有做出来不应该。

显然是backtracking.

分两种情况:

  一种是到当前位置的字母重新开始计数

  一种是继续前一个字母的计数

需要注意的是,如果cnt==0是不要加到结果String里的

 

 1     public List<String> generateAbbreviations(String word) { 2         List<String> res = new ArrayList<String>(); 3         if(word == null) { 4             return res; 5         } 6         generate(res, word, 0, "", 0); 7         return res; 8     } 9     10     private void generate(List<String> res, String word, int index, String cur, int cnt) {11         if(index == word.length()) {12             res.add(cur + ((cnt == 0)?"":cnt));13             return;14         }15         generate(res, word, index + 1, cur, cnt + 1);16         generate(res, word, index + 1, cur + ((cnt == 0)?"":cnt) + word.charAt(index) , 0);17     }

 

320. Generalized Abbreviation