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;
}