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

Example:

Given word = “word”, return the following list (order does not matter):

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

Backtracking

算是一道典型的回溯法的题目,做回溯法的题目,一定要先画遍历树,树画出来了,也就知道怎么写了。

用数字来代替子母,如果是生成word[start … legnth - 1]这一部分,数字可以取[0, length - start]

  1. 如果是0,就用当前字符word[start]
  2. 如果是(0, length - start),就用 i 再加上字符word[start + i]
  3. 如果正好等于length - start, 就直接用数字i就可以了

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public List<String> generateAbbreviations(String word) {
List<String> ans = new ArrayList<>();
StringBuilder sb = new StringBuilder();
backtracking(word, 0, ans, sb);
return ans;
}
private void backtracking(String word, int start, List<String> ans, StringBuilder sb) {
int n = word.length();
if (start == n) {
ans.add(sb.toString());
return;
}
for (int i = n - start; i >= 0; i--) {
if (i == 0) {
sb.append(word.charAt(start));
backtracking(word, start + 1, ans, sb);
sb.deleteCharAt(sb.length() - 1);
} else if (i == n - start) {
sb.append(i);
backtracking(word, n, ans, sb);
sb.delete(sb.length() - i / 10 - 1, sb.length());
} else {
sb.append(i);
sb.append(word.charAt(start + i));
backtracking(word, start + i + 1, ans, sb);
sb.delete(sb.length() - i / 10 - 2, sb.length());
}
}
}

论坛里总能找到又短又elegant的代码:

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

Bit Manipulation

tag里还标了位操作,我也想不到怎么做。这是在论坛里找的代码,但是性能并不好,也就懒得看了。
Ref: https://discuss.leetcode.com/topic/32190/o-m-n-bit-manipulation-java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<String> generateAbbreviations(String word) {
List<String> ret = new ArrayList<>();
int n = word.length();
for (int mask = 0; mask < (1 << n); mask++) {
int count = 0;
StringBuffer sb = new StringBuffer();
for (int i = 0; i <= n; i++) {
if (((1 << i) & mask) > 0) {
count++;
} else {
if (count != 0) {
sb.append(count);
count = 0;
}
if (i < n) sb.append(word.charAt(i));
}
}
ret.add(sb.toString());
}
return ret;
}