返回目录

题目描述

有一个字符串数组words 和一个字符串 chars。

假如可以用 chars 中的字母拼写出 words 中的某个“单词”（字符串），那么我们就认为你掌握了这个单词。

words 的字符仅由 a-z 英文小写字母组成，例如 "abc"

chars 由 a-z 英文小写字母和 "?" 组成。其中英文 "?" 表示万能字符，能够在拼写时当作任意一个英文字母。例如："?" 可以当作 "a" 等字母。

注意：每次拼写时，chars 中的每个字母和万能字符都只能使用一次。

输出词汇表 words 中你掌握的所有单词的个数。没有掌握任何单词，则输出0。

输入描述

第一行：输入数组 words 的个数，记作N。

第二行 \~ 第N+1行：依次输入数组words的每个字符串元素

第N+2行：输入字符串chars

输出描述

输出一个整数，表示词汇表 words 中你掌握的单词个数

备注

  • 1 ≤ words.length ≤ 100
  • 1 ≤ words[i].length, chars.length ≤ 100
  • 所有字符串中都仅包含小写英文字母、英文问号

示例：

输入4
cat
bt 
hat
tree
atach??
输出3
说明可以拼写字符串"cat"、"bt"和"hat"
输入3
apple
car
windown
welldoneapplec?
输出2
说明可以拼写字符串"apple"和“car”

题目解析

本题可以分别统计出chars和word中各字符的数量，然后遍历word每个字符c，比较word和chars中统计的c字符数量，如果word的c数量超过了chars的c数量，那么就就将超出数量计入diff中。

最终比较diff和chars中万能字符‘?’的数量，如果chars中万能字符‘?’的数量 >= diff，那么说明chars可以使用万能字符补足不同部分，即可以学会word。

Python算法源码


def char_statistic(s):
    cnts = [0] * 128  # 用于统计字符串中各字符的数量
  
    # 统计字符串中各字符的数量
    for char in s:
        cnts[ord(char)] += 1
  
    return cnts

def get_result(words, chars):
    ans = 0
    cnt_chars = char_statistic(chars)  # 统计输入字符串中各字符的数量
  
    # 遍历每个单词
    for word in words:
        diff = 0
        cnt_word = char_statistic(word)  # 统计单词中各字符的数量
    
        # 对比单词中各字符与输入字符串中对应字符的数量
        for j in range(128):
            diff += max(cnt_word[j] - cnt_chars[j], 0)
    
        # 如果单词中字符数量不超过输入字符串中对应字符数量，则计数加一
        if diff <= cnt_chars[ord('?')]:  # '?' 表示可以匹配任意字符
            ans += 1
  
    return ans

if __name__ == "__main__":
    n = int(input())  # 输入单词数量
    words = [input() for _ in range(n)]  # 输入单词列表
    chars = input()  # 输入字符
  
    # 输出符合条件的单词数量
    print(get_result(words, chars))

这段 Python 代码在每个关键步骤添加了注释，以便理解代码的功能和实现细节。

C算法源码

#include <stdio.h>
#include <string.h>

// 函数声明
void charStatistic(const char *s, int *cnts);
int getResult(const char **words, int n, const char *chars);

// 统计字符串中各字符的数量
void charStatistic(const char *s, int *cnts) {
    memset(cnts, 0, sizeof(int) * 128); // 初始化计数数组为0
  
    // 统计各字符数量
    while (*s) {
        cnts[(int)*s]++;
        s++;
    }
}

// 算法入口
int getResult(const char **words, int n, const char *chars) {
    int ans = 0;
    int cnt_chars[128];
  
    // 统计chars字符串中各字符的数量
    charStatistic(chars, cnt_chars);
  
    // 遍历单词列表
    for (int i = 0; i < n; i++) {
        int diff = 0;
        int cnt_word[128];
      
        // 统计word字符串中各字符的数量
        charStatistic(words[i], cnt_word);
      
        // 对比单词中各字符与输入字符串中对应字符的数量
        for (int j = 0; j < 128; j++) {
            diff += (cnt_word[j] > cnt_chars[j]) ? (cnt_word[j] - cnt_chars[j]) : 0;
        }
      
        // 如果单词中字符数量不超过输入字符串中对应字符数量，则计数加一
        if (diff <= cnt_chars['?']) {
            ans++;
        }
    }
  
    return ans;
}

int main() {
    int n;
    scanf("%d", &n); // 输入单词数量
  
    const char *words[n];
  
    // 输入单词列表
    for (int i = 0; i < n; i++) {
        char word[128];
        scanf("%s", word);
        words[i] = strdup(word);
    }
  
    char chars[128];
    scanf("%s", chars); // 输入字符
  
    // 输出符合条件的单词数量
    printf("%d\n", getResult(words, n, chars));
  
    // 释放单词内存
    for (int i = 0; i < n; i++) {
        free((void *)words[i]);
    }
  
    return 0;
}

Java算法源码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        String[] words = new String[n];
        for (int i = 0; i < n; i++) {
            words[i] = sc.next();
        }

        String chars = sc.next();

        System.out.println(getResult(words, n, chars));
    }

    public static int getResult(String[] words, int n, String chars) {
        int ans = 0;

        // 统计chars字符串中各字符的数量
        int[] cnt_chars = charStatistic(chars);

        for (int i = 0; i < n; i++) {
            int diff = 0;

            // 统计word字符串中各字符的数量
            int[] cnt_word = charStatistic(words[i]);

            for (int j = 0; j < 128; j++) {
                // 记录word的某字符超过chars的对应字符出现的数量
                diff += Math.max(cnt_word[j] - cnt_chars[j], 0);
            }

            if (diff <= cnt_chars['?']) {
                ans++;
                // System.out.println(words[i]);
            }
        }

        return ans;
    }

    public static int[] charStatistic(String s) {
        int[] cnts = new int[128];

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            cnts[c] += 1;
        }

        return cnts;
    }
}
最后修改：2024 年 03 月 31 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏