LeetCode刷题实战320：列举单词的全部缩写 / 四六文摘

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 列举单词的全部缩写，我们先来看题面：

https://leetcode-cn.com/problems/generalized-abbreviation/

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

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

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

示例

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

解题

迭代的方法，在之前出现过的字符串的基础上，接着更新新的可能的字符串的组成。

class Solution {
public:
    vector<string> generateAbbreviations(string word) {
        int len=word.size();
        vector<string> res;
        res.push_back("");//初始结果
        for(int i=0;i<len;++i){
            string w=word.substr(i,1);//对每个字符位置进行处理
            int nums_s=res.size();
            //对之前出现过的每种结果进行更新
            for(int j=0;j<nums_s;++j){
                string tmp=res[j];
                res[j]+=w;//更新加上当前字符的方式

        //更新转成当前数字的方式
                int k=tmp.size();
                //找出当前字符串的末尾的数字
                while(k>0&&isdigit(tmp[k-1])){
                    --k;
                }
                //根据当前字符串的末尾的字符是否是数字的情形，更新
                if(k==tmp.size()){
                    res.push_back(tmp+"1");
                }
                else{
                    res.push_back(tmp.substr(0,k)+to_string(1+stoi(tmp.substr(k,tmp.size()-k))));
                }
            }
        }
        return res;
    }
};