原题是lc320
Java代码：
public class Solution {public List<String> generateAbbreviations(String word){List<String> ans = new ArrayList<String>();backtrack(ans, new StringBuilder(), word, 0, 0);return ans;}// i is the current position// k is the count of consecutive abbreviated charactersprivate void backtrack(List<String> ans, StringBuilder builder, String word, int i, int k){int len = builder.length(); // keep the length of builderif(i == word.length()){if (k != 0) builder.append(k); // append the last k if non zeroans.add(builder.toString());} else {// the branch that word.charAt(i) is abbreviatedbacktrack(ans, builder, word, i + 1, k + 1);// the branch that word.charAt(i) is keptif (k != 0) builder.append(k);builder.append(word.charAt(i));backtrack(ans, builder, word, i + 1, 0);}builder.setLength(len); // reset builder to the original state}
}
错误1：
用Python的string代替string builder。因为string是immutable，在下一次递归时不会改变。
错误2：
class Solution(object):def generateAbbreviations(self, word):""":type word: str:rtype: List[str]"""def backtrack(ans, builder, word, i, k):length = len(builder)if i == len(word):if k != 0:builder.append(str(k))ans.append("".join(builder[:]))# return # don't do this, once you return, some branch can't call popelse:backtrack(ans, builder, word, i+1, k+1)if k != 0:builder.append(str(k))builder.append(word[i])backtrack(ans, builder, word, i+1, 0)# builder = builder[:length] # dont do this, slicing produces a new copy, this builder is that builder before!!!while len(builder) != length:builder.pop()ans = []backtrack(ans, [], word, 0, 0)return ans
用builder = builder[:length]来代替Java的setLength，错误在于Python切片会产生新的list，此builder非builder
错误3：多写一个return（如上所示）。
这会导致有些分支在返回以后没办法执行pop()。