当前位置:   article > 正文

【LeetCode-1160】拼写单词_有一个字符串数组 words 和一个字符串 chars. 假如可以用 chars 中的字母拼写出 w

有一个字符串数组 words 和一个字符串 chars. 假如可以用 chars 中的字母拼写出 w

2.1 拼写单词【1160】

2.1.1 题目描述

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

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

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

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

2.1.2 方法一:哈希表计数

思路和算法

显然,对于一个单词 word,只要其中的每个字母的数量都不大于 chars 中对应的字母的数量,那么就可以用 chars 中的字母拼写出 word。所以我们只需要用一个哈希表存储 chars 中每个字母的数量,再用一个哈希表存储 word 中每个字母的数量,最后将这两个哈希表的键值对逐一进行比较即可。

代码

class Solution {
    public int countCharacters(String[] words, String chars) {
        Map<Character, Integer> charsCnt = new HashMap<Character, Integer>();
        int length = chars.length();
        for (int i = 0; i < length; ++i) {	// 统计字母表中各字母出现次数
            char c = chars.charAt(i);
            charsCnt.put(c, charsCnt.getOrDefault(c, 0) + 1);
        }
        int ans = 0;
        for (String word : words) {
            Map<Character, Integer> wordCnt = new HashMap<Character, Integer>();
            int wordLength = word.length();
            for (int i = 0; i < wordLength; ++i) {	// 统计词汇表中每个单词字母出现的次数
                char c = word.charAt(i);
                wordCnt.put(c, wordCnt.getOrDefault(c, 0) + 1);
            }
            boolean isAns = true;
            for (int i = 0; i < wordLength; ++i) {
                char c = word.charAt(i);
                // 比较词汇表中单词的个数 < 单词字母的个数 则该单词未掌握
                if (charsCnt.getOrDefault(c, 0) < wordCnt.getOrDefault(c, 0)) {
                    isAns = false;
                    break;
                }
            }
            if (isAns) {
                ans += word.length();
            }
        }
        return ans;
    }
}
  • 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

复杂度分析

  • 时间复杂度:O(n),其中 n 为所有字符串的长度和。我们需要遍历每个字符串,包括 chars 以及数组 words 中的每个单词。

  • 空间复杂度:O(S),其中 S 为字符集大小,在本题中 S 的值为 26(所有字符串仅包含小写字母)。程序运行过程中,最多同时存在两个哈希表,使用的空间均不超过字符集大小 S,因此空间复杂度为 O(S)。

2.1.3 my answer—map计数

class Solution {
        public int countCharacters(String[] words, String chars) {
        Map<Character,Integer> map = new HashMap<>();
        char[] chars1 = chars.toCharArray();
        for (int i = 0; i < chars1.length; i++) {
            Character ch = chars1[i];
            map.put(ch, map.getOrDefault(ch,0)+1);
        }
        int sum = 0;
        for (int i = 0; i < words.length; i++) {
            boolean flag = true;
            char[] chars2 = words[i].toCharArray();
            Map<Character,Integer> map1 = new HashMap<>(map);	// 深拷贝一份字母表统计数据
            for (int j = 0; j < chars2.length; j++) {
                Character ch = chars2[j];
                if(map1.containsKey(ch)){
                    if(map1.get(ch)>0){
                        map1.put(ch, map1.get(ch)-1);
                    }else {
                        flag = false;
                        break;
                    }
                }else {
                    flag = false;
                    break;
                }
            }
            if(flag){
                sum += chars2.length;
            }
        }
        return sum;
    }
}
  • 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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/705328
推荐阅读
相关标签
  

闽ICP备14008679号