赞
踩
博主这半年来一直在主要学习Java的有关知识,疏忽了对算法的训练,偶得一著名刷题网站LeetCode,出于对算法的热爱,便决定开始刷题一段时间,加上前几天给我推送了周赛的消息,便报了名。为了巩固Java的知识,便选择了用Java语言来coding。
虽然开始前的紧张中带着几分的憧憬,但是打开第一题便目瞪口呆,有题云:
给你一份『词汇表』(字符串数组) 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.1 <= words.length <= 1000
2.1 <= words[i].length, chars.length <= 100
3.所有字符串中都仅包含小写英文字母
我尝试了很多种方法,因为对Java的API并没有做到非常熟悉,所以很多方法都不会用,写出的代码甚至连编译都过不了,便在结束之后,看了排名第一的大佬的代码,叹为妙绝,因为大佬写的是C++代码,便在理解之后,改为了Java代码
代码如下
class Solution { public int countCharacters(String[] words, String chars) { // 统计字母表的字母出现次数 int[] chars_count = count(chars); int res = 0; for (String word : words) { // 统计单词的字母出现次数 int[] word_count = count(word); if (contains(chars_count, word_count)) { res += word.length(); } } return res; } // 检查字母表的字母出现次数是否覆盖单词的字母出现次数 boolean contains(int[] chars_count, int[] word_count) { for (int i = 0; i < 26; i++) { if (chars_count[i] < word_count[i]) { return false; } } return true; } // 统计 26 个字母出现的次数 int[] count(String word) { int[] counter = new int[26]; for (int i = 0; i < word.length(); i++) { char c = word.charAt(i); counter[c-'a']++; } return counter; } }
这个题的思路在处理字符串问题中很常见,开两个26个int长度的一维数组,每个元素存储对应字母的数量,s数组存储的是字母表字母的数量,t数组存储词汇表每个词汇的字母数量,在用一次for循环来判断两张表对应字母的数量,只有当每一个字母在词汇表中出现的次数小于字母表时,才能够将词汇的长度加到ans中,等到最外层for循环结束,返回ans。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。