My code:
public class Solution {
public List<String> generateAbbreviations(String word) {
List<String> ret = new ArrayList<String>();
if (word == null) {
return ret;
}
helper(word, 0, "", 0, ret);
return ret;
}
private void helper(String word, int position, String curr, int counter, List<String> ret) {
if (position >= word.length()) {
if (counter > 0) {
curr += counter;
}
ret.add(curr);
}
else {
helper(word, position + 1, curr, counter + 1, ret); // abbreviate
helper(word, position + 1, curr + (counter > 0 ? counter : "") + word.charAt(position), 0, ret); // add character
}
}
}
这道题目看答案的。感觉挺怪，google的题目。
backtracking
reference:
https://discuss.leetcode.com/topic/32270/java-backtracking-solution
当指针移动到index处时，我们有两个选择。
要么， abbreviate this character,
要么， 将这个character 插入到current string中
如果打算abbreviate, 那么counter + 1
如果打算插入到当前string中，那就将前面abbreviate 的字符兑现。如果counter > 0,就先插一个数字进去，在跟上当前的字母。
Anyway, Good luck, Richardo! -- 09/02/2016
