题目

Write a function to generate the generalized abbreviations of a word.

Note: The order of the output does not matter.

Example:

Input: "word"
Output:
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]


回溯算法

• 要么缩写用1代替（相邻的1可以融合）
• 要么不用缩写

代码

class Solution {
public List<String> generateAbbreviations(String word) {
List<String> res = new ArrayList<>();
if (word == null) { return null; }
backtracking(new StringBuilder(), word, 0, 0, res);
return res;
}
//这里回溯稍微有点复杂，但抓住关键就不会错：
//回溯的主体是prefix，所以只有当prefix真正改变了，才需要调用delete()回溯。
//每次递归展开两条支线：
//      1. 数字支线：prefix暂不变化，暂记一位缩写，所以本层递归不回溯。哪里遇到字符了，缩写兑现到prefix里了，再回溯。
//      2. 字符支线：本层递归prefix就变化，而且带着之前所有累计的缩写位数一起兑现到prefix里，所以当场回溯。
//
private void backtracking(StringBuilder prefix, String word, int p, int count, List<String> list) {
//base case
if (p == word.length()) {
if (count > 0) {
int len = prefix.length();
prefix.delete(len,prefix.length()); //数字线在这里真正加到prefix里之后回溯
} else {
}
return;
}
//数字支线
backtracking(prefix,word,p+1,count+1,list); //数字支线这里没有真的改变prefix，先不回溯
//字符支线
int len = prefix.length();
if (count > 0) { prefix.append(String.valueOf(count)); }
prefix.append(word.charAt(p));
backtracking(prefix,word,p+1,0,list);
prefix.delete(len,prefix.length());         //字符支线因为已经改变prefix，所以在这里回溯
}
}


分两步走，回溯算法可以稍微简单一点

• 第一步，只替换（缩写用1替换字符），不融合（相邻的1不累加）
• 第二步，累加相邻的1

代码

class Solution {
public List<String> generateAbbreviations(String word) {
if (word == null) { return null; }
res = new ArrayList<String>();
charArray = word.toCharArray();
backtracking(0);
return res;
}
private List<String> res;
private char[] charArray;
private void backtracking(int p) {
if (p == charArray.length) {
return;
}
//保留字符分支，完全不需要动
backtracking(p+1);
//缩写成'1'分支，先改成'1'，然后回溯改回来
char c = charArray[p];
charArray[p] = '1';
backtracking(p+1);
charArray[p] = c;
}
private String merge(char[] word) {
int len = word.length;
StringBuilder sb = new StringBuilder();
int p = 0;
while (p < len) {
while (p < len && !Character.isDigit(word[p])) { sb.append(word[p]); p++; }
int count = 0;
while (p < len && Character.isDigit(word[p])) { p++; count++; }
if (count > 0) { sb.append(String.valueOf(count)); }
}
return new String(sb);
}
}