go语言题解LeetCode1160拼写单词示例详解

2022-12-30 193阅读 0评论

?=题目描述

1160. 拼写单词 - 力扣(leetcode

给你一份『词汇表』(字符串数组Words和一张『字母表』(字符串)chars

假如你可以用chars中的『字母』(字符)拼写出 words中的某个『单词』(字符串),那么我们就认为你掌握了这个单词。

注意:每次拼写(指拼写词汇表中的一个单词)时,chars 中的每个字母都只能用一次。

返回词汇表words中你掌握的所有单词的 长度之和

示例 1:

输入:words = ["cat","bt","hat","tree"], chars = "atach" 输出:6 解释:  可以形成字符串 "cat" 和 "hat",所以答案是 3 + 3 = 6。 

示例 2:

输入:words = ["hello","world","LeetCode"], chars = "welldonehoneyr" 输出:10 解释: 可以形成字符串 "hello" 和 "world",所以答案是 5 + 5 = 10。 

提示:

1 <= words.length <= 1000

1 <= words[i].length, chars.length<= 100

所有字符串中都仅含小写英文字母

思路分析

统计chars中各字母(字符)的个数

然后分别统计words字符串数组中的每个字符串的各个字母(字符)的个数

然后在26个对应位置作比较

若当前word字符串的对应位置字符数小于等于chars中对应位置字符数

则记录当前word字符串的长度

将其做为总长度的一部分

依次比较余下的word字符串,重复前面操作,最终得到总长度(答案)

AC 代码

class SolutiON { public int countCharacters(string[] words, String chars) { int n=chars.length(); int[] arr=new int[26]; for(int i=0;i<n;i++){ arr[chars.charAt(i)-'a']++; } int res=0; for(String word:words){ int[] arr1=new int[26]; for(int j=0;j<word.length();j++){ arr1[word.charAt(j)-'a']++; } for(int i=0;i<26;i++){ if(arr1[i]<=arr[i]) { if(i==25) res=res+word.length(); }else break; } } return res; } } 

参考

别人用int[26]解题思路

友情提示:遇到有提示字符串仅包含小写(或者大写)英文字母的题,

都可以试着考虑能不能构造长度为26的每个元素分别代表一个字母的数组,来简化计算

对于这道题,用数组c来保存字母表里每个字母出现的次数如法炮制,再对词汇表中的每个词汇都做一数组w,比较数组w与数组c的对应位置

如果w中的都不大于c,就说明该词可以被拼写出,长度计入结果如果w其中有一个超过了c,则说明不可以被拼写,直接跳至下一个(这里用到了带Label的continue语法

代码

class Solution { public int countCharacters(String[] words, String chars) { int[] c = new int[26]; for(char cc : chars.toCharArray()) { c[(int)(cc - 'a')] += 1; } int res = 0; a: for(String word : words) { int[] w = new int[26]; for(char ww : word.toCharArray()) { w[(int)(ww - 'a')] += 1; } for(int i=0; i<26; i++) { if(w[i] > c[i]) { continue a; } } res += word.length(); } return res; } } 

c++几乎双百的哈希解法

解题思路

1 构建chars的字符到数量映射表

2. 对于words里的每个单词也构建似一个表,构建后去遍历比较是否小于等于chars里的数量,否则失败

代码

class Solution { public: int countCharacters(vector<string>& words, string chars) { // 记录累计的长度之和 int res = 0; // 构建chars的映射表 int cnt[26]; memset(cnt, 0, sizeof(int)*26); for (char c : chars) { ++cnt[c-'a']; } ​​​​​​​// 遍历words去构建每个映射表,然后比较即可 int curr[26]; for (string word : words) { memset(curr, 0, sizeof(int)*26); for (char c : word) { ++curr[c-'a']; } bool IsOK= true; for (int i = 0; i < 26; ++i) { if (curr[i] > cnt[i]) { IsOK = false; break; } } if (IsOK) { res += word.size(); } } return res; } }; 

以上就是Go语言题解Leetcode1160拼写单词示例详解的详细内容,更多关于Go题解拼写单词的资料请关注云初冀北其它相关文章!

免责声明
本站提供的资源,都来自网络,版权争议与本站无关,所有内容及软件的文章仅限用于学习和研究目的。不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负,我们不保证内容的长久可用性,通过使用本站内容随之而来的风险与本站无关,您必须在下载后的24个小时之内,从您的电脑/手机中彻底删除上述内容。如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。侵删请致信E-mail:GOliszhou@gmail.com
$

发表评论

表情:
评论列表 (暂无评论,193人围观)

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