Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >LeetCode 408. 有效单词缩写

LeetCode 408. 有效单词缩写

作者头像
Michael阿明
发布于 2020-07-13 08:20:02
发布于 2020-07-13 08:20:02
1.2K00
代码可运行
举报
运行总次数:0
代码可运行

1. 题目

给一个 非空 字符串 s 和一个单词缩写 abbr ,判断这个缩写是否可以是给定单词的缩写。

字符串 “word” 的所有有效缩写为:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", 
 "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
注意单词 "word" 的所有有效缩写仅包含以上这些。
任何其他的字符串都不是 "word" 的有效缩写。

注意:
假设字符串 s 仅包含小写字母且 abbr 只包含小写字母和数字。

示例 1:
给定 s = "internationalization", abbr = "i12iz4n":
函数返回 true.
 
示例 2:
给定 s = "apple", abbr = "a2e":
函数返回 false.

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/valid-word-abbreviation 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

  • 易错例子
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
"a"
"01"
预期:
false

"internationalization"
"i5a11o1"
预期:
true
  • 等效长度一致
  • 数字不能有前导零
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    bool validWordAbbreviation(string word, string abbr) {
    	int i = 0, n = 0, j = 0;
    	while(i<word.size() && j < abbr.size())
    	{
    		n = 0;
            if(isdigit(abbr[j]))
            {   
                if(abbr[j]=='0')//"a","01"
                    return false;
                while(j < abbr.size() && isdigit(abbr[j]))
                    n = n*10+abbr[j++]-'0';
            }
    		i += n;
    		if(i<word.size() && j<abbr.size() && word[i] != abbr[j])
    			return false;
    		else if((i<word.size()&&j>=abbr.size())||(i>=word.size()&&j<abbr.size()))
    			return false;
            else if(i==word.size() && j==abbr.size())
                return true;//这里加一条,可能以数字结尾,下面++,出了循环,最后条件不成立
            i++,j++;
    	}
    	return i==word.size() && j==abbr.size();
    }
};

4 ms 6 MB

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/07/03 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
​LeetCode刷题实战527:单词缩写
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
程序员小猿
2022/03/03
3850
​LeetCode刷题实战408:有效单词缩写
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
程序员小猿
2021/10/21
6040
​LeetCode刷题实战411:最短独占单词缩写
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
程序员小猿
2021/10/21
4500
​LeetCode刷题实战411:最短独占单词缩写
​LeetCode刷题实战320:列举单词的全部缩写
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
程序员小猿
2021/07/29
2890
LeetCode 320. 列举单词的全部缩写(回溯/位运算)
文章目录 1. 题目 2. 解题 2.1 回溯 2.2 位运算 1. 题目 请你写出一个能够举单词全部缩写的函数。 注意:输出的顺序并不重要。 示例: 输入: "word" 输出: ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/
Michael阿明
2021/02/19
5730
【python-子集】Generalized Abbreviation(广义缩写)
Write a function to generate the generalized abbreviations of a word.
西西嘛呦
2020/08/26
6520
LeetCode 288. 单词的唯一缩写(哈希)
假设你有一个字典和一个单词,请你判断该单词的缩写在这本字典中是否唯一。 若单词的缩写在字典中没有任何 其他 单词与其缩写相同,则被称为单词的唯一缩写。
Michael阿明
2020/07/13
8460
leetcode每日一题:290. 单词规律
题目链接:https://leetcode-cn.com/problems/word-pattern
用户3578099
2020/12/30
4800
LeetCode 527. 单词缩写(Trie树)
给定一个由n个不重复非空字符串组成的数组,你需要按照以下规则为每个单词生成最小的缩写。
Michael阿明
2021/02/19
7190
【面试高频题】难度 1/5,可用 Trie 进阶的模拟题
给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词,该单词是由 words 词典中其他单词逐步添加一个字母组成。
宫水三叶的刷题日记
2022/10/30
2570
LeetCode 211. 添加与搜索单词 - 数据结构设计(Trie树)
void addWord(word) bool search(word) search(word) 可以搜索文字或正则表达式字符串,字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。
Michael阿明
2020/07/13
4420
LeetCode 211. 添加与搜索单词 - 数据结构设计(Trie树)
拼写单词(leetcode 1160)
给你一份『词汇表』(字符串数组) words 和一张『字母表』(字符串) chars。 假如你可以用 chars 中的『字母』(字符)拼写出 words 中的某个『单词』(字符串),那么我们就认为你掌握了这个单词。 注意:每次拼写(指拼写词汇表中的一个单词)时,chars 中的每个字母都只能用一次。 返回词汇表 words 中你掌握的所有单词的长度之和。
恋喵大鲤鱼
2022/09/27
3290
【leetcode刷题】T79-检测大写字母
全为大写字母、全为小写字母,都是返回True;两者都有,则只能第一个字母是大写字母,其他为小写字母,返回True,其他返回False。
木又AI帮
2019/07/17
5750
☆打卡算法☆LeetCode 30、串联所有单词的子串 算法解析
“给定一个单词数组,匹配另一个数组中是否存在这个单词数组中所有的串联单词,返回起始位置。”
恬静的小魔龙
2022/08/07
2320
☆打卡算法☆LeetCode 30、串联所有单词的子串  算法解析
☆打卡算法☆LeetCode 79、单词搜索 算法解析
“给定一个二维数组和一个单词,如果单词存在网格中返回true,否则返回false。”
恬静的小魔龙
2022/08/07
3600
☆打卡算法☆LeetCode 79、单词搜索  算法解析
LeetCode 720. 词典中最长的单词(Trie树)
给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词,该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案,则返回答案中字典序最小的单词。
Michael阿明
2020/07/13
8260
LeetCode 720. 词典中最长的单词(Trie树)
数字问题-LeetCode 507、508、513、515、516、520、518(DP、BFS)
LeetCode # 507 508 509 513 515 516 520 518
算法工程师之路
2020/02/13
4570
【算法千题案例】每日LeetCode打卡——91.词典中最长的单词
思路解析 对于每个单词,我们可以检查它的全部前缀是否存在,可以通过 Set 数据结构来加快查找
呆呆敲代码的小Y
2021/12/11
4110
Leetcode 212 Word Search II 字典树 + 回溯
Given a 2D board and a list of words from the dictionary, find all words in the board. Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell
triplebee
2018/01/12
5680
Google 面试题分析 | 字典里面的最长单词
描述 给定一个字符串列表words,找到words最长的word,使得这个word可用words中的其他word一次一个字符地构建。如果有多个可选答案,则返回最长的且具有最小字典序的word。 样例 Ⅰ. Input: words =["w","wo","wor","worl","world"]     Output: "world"     Explanation: “world”可通过”w”, “wo”, “wor”, “worl”一次一个字符进行构建。 Ⅱ . Input: words =["a",
汤高
2018/01/11
8940
推荐阅读
相关推荐
​LeetCode刷题实战527:单词缩写
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档