当前位置:   article > 正文

LeetCode周赛——拼写单词_给你一份『词汇表』(字符串数组) words 和一张『字母表』(字符串) chars。 假如你

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

博主这半年来一直在主要学习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。
  • 1
  • 2
  • 3
  • 4

示例2:

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

提示:
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;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

这个题的思路在处理字符串问题中很常见,开两个26个int长度的一维数组,每个元素存储对应字母的数量,s数组存储的是字母表字母的数量,t数组存储词汇表每个词汇的字母数量,在用一次for循环来判断两张表对应字母的数量,只有当每一个字母在词汇表中出现的次数小于字母表时,才能够将词汇的长度加到ans中,等到最外层for循环结束,返回ans。

声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop】
推荐阅读
相关标签
  

闽ICP备14008679号