LEETCODE 320. Generalized Abbreviation 解题思路分析

题目大意：

列举单词的全部缩写

请你写出一个能够举单词全部缩写的函数。

注意：输出的顺序并不重要。

示例:

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=320

解题思路分析：

个人感觉这是一道dfs题目，dfs递归函数中，我们需要定义两个重要的参数，一个是，当前位置前已经连续缩写的位数N。另一个是除去缩写位数之外的字符串S。S+N是组合后的缩写字符串。递归函数由字符串起始位置递归到末尾，对于字符串的每一位

1. 使用当前字符，此时S变为S+N+当前字符，N变为0。
2. 当前字符与前面组成一个数字。此时S不变，N变为N+1。

当递归到字符串末尾时，将S+N保存进返回列表。

实现代码：

List<String> res = new ArrayList<>(); // 返回结果
public List<String> generateAbbreviations(String word) {
    // dfs所有情况
    help(word, 0, new StringBuilder(), 0);
    return res;
}
// word为原始字符串
// index为当前位置
// temp为当前组成的缩略字符串
// abb为当前缩略长度
void help(String word, int index, StringBuilder temp, int abb){
    // 当递归到完所有字符之后
    if(index==word.length()){
        // 如果存在缩略长度，将其加入temp
        if(abb>0) temp.append(abb);
        // 将temp加入返回结果
        res.add(temp.toString());
        return;
    }
    StringBuilder newTemp = new StringBuilder(temp);
    // 当前字符
    char c = word.charAt(index);
    // 不缩略当前字符
    // 如果存在缩略长度，将其加入temp
    if(abb>0) newTemp.append(abb);
    // 将当前字符加入temp
    newTemp.append(c);
    // 不缩略当前字符继续递归
    help(word, index+1, newTemp, 0);
    // 缩略当前字符继续递归
    help(word, index+1, temp, abb+1);
}

本题解法执行时间为9ms。

Runtime: 9 ms, faster than 64.91% of Java online submissions for Generalized Abbreviation.

Memory Usage: 47.2 MB, less than 100.00% of Java online submissions for Generalized Abbreviation.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-320-generalized-abbreviation-解题思路分析/