目录题目描述思路分析AC 代码 别人用int[26] 解题思路代码c++几乎双百的哈希解法代码题目描述 1160. 拼写单词 - 力扣(LeetCode) 给
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字符串,重复前面操作,最终得到总长度(答案)
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;
}
}
参考
友情提示:遇到有提示字符串仅包含小写(或者大写)英文字母的题,
都可以试着考虑能不能构造长度为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;
}
}
解题思路
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题解拼写单词的资料请关注编程网其它相关文章!
--结束END--
本文标题: go语言题解LeetCode1160拼写单词示例详解
本文链接: https://www.lsjlt.com/news/176272.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-04-05
2024-04-05
2024-04-05
2024-04-04
2024-04-05
2024-04-05
2024-04-05
2024-04-05
2024-04-04
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0