[动态规划,字符串操作] 分词

第五题：分词

题目描述

给定一个包含n个单词的英文词典和m个只由英文字母组成的字符串。
判断这些字符串能否由词典中的单词组成。
比如词典中包含5个单词：“Jim”, “and”, “cat”,“like”, “dog”
这些单词能组成"Jimlikecatanddog"、“doglikecatandcatlikedog"等，
但是不能组成"catlikeme”
为了简化问题，所有的字母都是小写,而且词典中的所有单词长度都一样。

关于输入

第一行两个正整数，n和m（n，m都不超过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 1000

int 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; cin>>n>>m;
    getchar();
    string words[n];
    for(int i=0;i<n;i++){
        cin>>words[i];
    }
    for(int i=0;i<m;i++){
        string s; cin>>s;
        string temp(s.size(),' ');
        for(int i=0;i<n;i++){
            while(s.find(words[i])!=string::npos){
                int len=words[i].size();
                int p=s.find(words[i]);
                for(int j=p;j<p+len;j++){
                    s[j]=' ';
                }
            }
        }
        if(s==temp){
            cout<<"Yes"<<endl;
        }
        else cout<<"No"<<endl;
    }
	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 更安全的选择，因为它不会因为字符串未以空字符结尾而导致访问越界。
返回值：根据比较结果返回不同的整数值。