dw设计试图做网站,WordPress文章底部广告插件,南宁网页设计价格,专业app软件定制第五题#xff1a;分词
题目描述
给定一个包含n个单词的英文词典和m个只由英文字母组成的字符串。 判断这些字符串能否由词典中的单词组成。 比如词典中包含5个单词#xff1a;“Jim”, “and”, “cat”,“like”, “dog” 这些单词能组成Jimlikecatanddog、“…第五题分词
题目描述
给定一个包含n个单词的英文词典和m个只由英文字母组成的字符串。 判断这些字符串能否由词典中的单词组成。 比如词典中包含5个单词“Jim”, “and”, “cat”,“like”, “dog” 这些单词能组成Jimlikecatanddog、“doglikecatandcatlikedog等 但是不能组成catlikeme” 为了简化问题所有的字母都是小写,而且词典中的所有单词长度都一样。
关于输入
第一行两个正整数n和mnm都不超过100 接下来n行每行一个单词每个单词长度不超过20 接下来m行每行一个字符串长度不超过1000
关于输出
m行表示词库中的单词能否组成该字符串能输出Yes不能输出No。
例子输入
10 5 did not and but hit run cat dog pig cow cathitdoganddogrun doghitpigbutpigdidnotrun pighitcowandcowdidrun cowhitcatandcatcry catdogpigandcowarehungry
例子输出
Yes Yes Yes No No
解题分析
要解决这个问题我们可以使用一种称为“动态规划”的方法。这种方法的核心是从字符串的开头开始逐步检查每个可能的词典单词看它是否出现在当前位置。如果找到一个词典中的单词我们就标记这个位置然后从这个位置之后的字符串继续重复这个过程。如果能找到一种方式使得整个字符串都被词典中的单词覆盖那么答案就是Yes否则是No。
以下是使用C语言实现这个算法的步骤
读取输入首先读取n和m的值然后读取所有的词典单词和要检查的字符串。
初始化动态规划数组创建一个布尔型数组 dp其中 dp[i] 表示字符串的前 i 个字符能否被词典中的单词完全覆盖。初始化 dp[0] true因为空字符串总是可以被覆盖。
动态规划求解对于每个字符串从左到右遍历。对于每个位置 i遍历词典中的所有单词。如果当前位置之前的字符串可以被覆盖即 dp[i - wordLength] true并且从位置 i - wordLength 开始的子字符串是词典中的一个单词那么将 dp[i] 设置为 true。
输出结果如果 dp[strlen(str)] 是 true则输出 “Yes”否则输出 “No”。
代码实现
#include stdio.h
#include string.h
#include stdbool.h#define MAX_WORDS 100
#define MAX_WORD_LENGTH 20
#define MAX_STRING_LENGTH 1000int n, m;
char dictionary[MAX_WORDS][MAX_WORD_LENGTH 1];
char str[MAX_STRING_LENGTH 1];bool canFormString() {int len strlen(str);bool dp[len 1];memset(dp, false, sizeof(dp));dp[0] true;for (int i 0; i len; i) {if (!dp[i]) continue;for (int j 0; j n; j) {int wordLen strlen(dictionary[j]);if (i wordLen len strncmp(str[i], dictionary[j], wordLen) 0) {dp[i wordLen] true;}}}return dp[len];
}int main() {scanf(%d %d, n, m);for (int i 0; i n; i) {scanf(%s, dictionary[i]);}for (int i 0; i m; i) {scanf(%s, str);if (canFormString()) {printf(Yes\n);} else {printf(No\n);}}return 0;
}
当然如果我们使用c中string的find函数本题显然可以不用动态规划 方法二
#include iostream
using namespace std;int main() {int n,m; cinnm;getchar();string words[n];for(int i0;in;i){cinwords[i];}for(int i0;im;i){string s; cins;string temp(s.size(), );for(int i0;in;i){while(s.find(words[i])!string::npos){int lenwords[i].size();int ps.find(words[i]);for(int jp;jplen;j){s[j] ;}}}if(stemp){coutYesendl;}else coutNoendl;}return 0;
}
进一步拓展
strncmp 函数是 C 语言标准库中用于比较两个字符串的函数它可以比较两个字符串的前 n 个字符。这个函数定义在 string.h 头文件中。它的原型如下
int strncmp(const char *s1, const char *s2, size_t n);s1第一个字符串的指针。s2第二个字符串的指针。n要比较的最大字符数。
strncmp 函数的行为和特点包括 比较字符它从两个字符串的开始处开始比较直到遇到不同的字符或比较了 n 个字符为止。 比较结果 如果在比较了 n 个字符之前 s1 和 s2 是相同的函数返回 0。如果在比较了 n 个字符之前在 s1 中的字符小于 s2 中的相应字符根据 ASCII 值函数返回一个小于 0 的值。如果在比较了 n 个字符之前在 s1 中的字符大于 s2 中的相应字符函数返回一个大于 0 的值。 字符串长度如果两个字符串的前 n 个字符是相同的但它们的长度不同strncmp 只比较前 n 个字符因此认为这两个字符串是相等的。 安全性strncmp 是比 strcmp 更安全的选择因为它不会因为字符串未以空字符结尾而导致访问越界。 返回值根据比较结果返回不同的整数值。
strncmp 函数常用于比较有长度限制的字符串或者在不确定字符串是否以空字符结尾的情况下进行安全的字符串比较。使用时需要确保比较的字符数 n 不超过两个字符串中任一个的长度。
