lintcode 779. 广义缩写dfs

你的名字 2023-05-22 22:20 1阅读 0赞

请完成一个能够给出 wordword 的所有“缩写”的函数（给出任意一种排列即可）

样例
    例1:
    
    输入: 
    word = "word", 
    输出: 
    ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]
    例2:
    
    输入:
    word = "today"
    输出:
    ["1o1a1","1o1ay","1o2y","1o3","1od1y","1od2","1oda1","1oday","2d1y","2d2","2da1","2day","3a1","3ay","4y","5","t1d1y","t1d2","t1da1","t1day","t2a1","t2ay","t3y","t4","to1a1","to1ay","to2y","to3","tod1y","tod2","toda1","today"]

class Solution {
        
    public:
        /**
         * @param word: the given word
         * @return: the generalized abbreviations of a word
         */
        vector<string> generateAbbreviations(string &word) {
        
            // Write your code here
            vector<string>res;
            string tmp="";
            dfs(word,res,0,tmp,0);
            return res;
        }
        void dfs(string &word,vector<string>&res,int index,string tmp,int cnt)
        {
        
            if(index==word.size()){
        
                if(cnt>0) tmp+=to_string(cnt);
                res.push_back(tmp);
                return;
            }
            dfs(word,res,index+1,tmp,cnt+1);
            if(cnt>0) tmp+=to_string(cnt)+word[index];
            else tmp+=word[index];
            dfs(word,res,index+1,tmp,0);
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，1人围观）

还没有评论，来说两句吧...

相关阅读

相关 lintcode 677. 大岛的数量 dfs

给一个布尔类型的二维数组, 0 表示海, 1 表示岛。如果两个1是相邻的,那么我们认为他们是同一个岛.我们只考虑上下左右相邻. 找到大小在 k 及 k 以上的岛屿的数量

r囧r小猫/ 2023年07月24日 14:38/ 0 赞/ 6 阅读

相关 lintcode 779. 广义缩写dfs

请完成一个能够给出 wordword 的所有“缩写”的函数（给出任意一种排列即可）样例例1: 输入: word = "word

你的名字/ 2023年05月22日 22:20/ 0 赞/ 2 阅读

相关 lintcode 680. 分割字符串 dfs

给一个字符串,你可以选择在一个字符或两个相邻字符之后拆分字符串,使字符串由仅一个字符或两个字符组成,输出所有可能的结果样例样例1 输入：

浅浅的花香味﹌/ 2023年05月22日 06:41/ 0 赞/ 3 阅读

相关广义表

广义表(广义表也称为列表，是线性表的一种推广，也是数据元素的有序序列) 一、基础 1.如何设定链表结点?广义表中的数据元素可能为单元素(原子)或子表，由此需要两种结点:

我就是我/ 2022年12月07日 04:26/ 0 赞/ 245 阅读

相关题目779 兰州烧饼

![20160729150127458][] 已AC代码： include<cstdio> using namespace std;

浅浅的花香味﹌/ 2022年09月24日 11:18/ 0 赞/ 106 阅读

相关广义表

广义表的定义： ![20160528163216384][] 在广义表中约定： ① 第一个元素是表头，而其余元素组成的表称为表尾； ② 用小写字母表示原子类型，用大写字

ゝ一纸荒年。/ 2022年08月22日 13:17/ 0 赞/ 282 阅读

相关广义表

1.定义广义表(Lists，又称列表)是一种非线性的[数据结构][Link 1]，是[线性表][Link 2]的一种推广。即广义表中放松对表元素的原子限制，容

太过爱你忘了你带给我的痛/ 2022年08月20日 13:15/ 0 赞/ 219 阅读

相关 779C - Dishonest Sellers

C. Dishonest Sellers Igor found out discounts in a shop and decided to buy n items. D

不念不忘少年蓝@/ 2022年07月10日 12:27/ 0 赞/ 125 阅读

相关【CodeForces 779A】Pupils Redistribution（模拟）

A. Pupils Redistribution time limit per test 1 second memory limit per test 256

待我称王封你为后i/ 2022年07月08日 14:28/ 0 赞/ 187 阅读

相关通过【lintCode-15全排列问题】学习DFS算法

这周发现毕业一年后自己对于技术的激情好像变得已经没有以前那么热爱与执着了，不再像以前那样每天想着都在学习新的技术，也不再因为每天没有学习到新的东西而会感到负罪感。也或许是我在大

小咪咪/ 2022年05月18日 07:52/ 0 赞/ 199 阅读