[LeetCode]——拼写单词

NO.1160 拼写单词简单

思路一：哈希表 map先统计chars字符以及每个字符的数量。遍历words每个单词，遍历每个单词每个字符如果字符存在map中就加入临时表并统计数量，如果当前字符不存在或者数量超了都将有效标志置为false。最后如果当前单词有效就将长度加入到结果中。

public int countCharacters(String[] words, String chars) {
    if (chars==null||chars.length()<1)return 0;
    //统计chars
    HashMap<Character,Integer> map=new HashMap<>();
    for (int i = 0; i < chars.length(); i++) {
        Integer value = map.getOrDefault(chars.charAt(i), 0);
        map.put(chars.charAt(i),value+1);
    }
    //遍历每个单词
    int count=0;
    for (int i = 0; i < words.length; i++) {
        //临时长度遍历，临时表，有效标志
        int temp=0;
        HashMap<Character,Integer> has=new HashMap<>();
        boolean ok=true;
        //遍历单词每个字符
        for (int j = 0; j < words[i].length(); j++) {
            //存在于map
            if (map.containsKey(words[i].charAt(j))){
                int value=has.getOrDefault(words[i].charAt(j),0);
                has.put(words[i].charAt(j),value+1);
                temp++;
                //数量超了
                if (has.get(words[i].charAt(j))>map.get(words[i].charAt(j))){
                    ok=false;
                    break;
                }
            }else {//不存在于map
                ok=false;
                break;
            }
        }
        //如果有效加入结果
        if (ok)count+=temp;
    }
    return count;
}

时间复杂度：O(n+m) n是words字符数量，m是chars字符数量。

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.1160 拼写单词 简单

NO.1160 拼写单词简单