检查字符串是否可以由较小的字符串组合而成

Question

检查字符串是否可以由较小的字符串组合而成

calgorithm

3

如何检查一个字符串是否可以完全由'n'个其他字符串连接而成，其中'n'是一个变量？

例如：

catdogmice 由字符串cat、dog和mice组成，但catdogmices则不是。

Edit1：这是我写的一个代码（抱歉，我对编码没有基础，写了很糟糕的代码，它会导致段错误）

#include<stdio.h>
#include<string.h>
char words[1001][11];
char* str;
int flag;
void autopsy(char* str, int m)
{

        if(strcmp(str,'\0')==0)
                flag = 1;
        int len, i;
        for(i = 0; i < m; i++)
        {
                len = strlen(words[i]);
                if(strncmp(words[i], str, len)==0)
                {
                        *str += len;
                        autopsy(str, m);
                }
        }
        if(flag == 1)
                printf("YES\n");
        else
                printf("NO\n");
}

int main()
{
        int m, l, i;
        scanf("%d %d", &m, &l);
        for(i = 0; i < m; i++)
                scanf("%s", words[i]);
        int t;
        scanf("%d", &t);
        while(t--)
        {
                flag = 0;
                gets(str);
                autopsy(str, m);
        }
        return 0;
}

首先，我读取较小单词的数量和最大长度。然后我读取要检查的较大字符串的数量，并输出是否可以形成。如何确保如果大单词是catsdog，我的单词是cat、cats和dog，那么首先删除cat，然后不能删除sdog，并给出答案为“否”，但实际答案是“是”。

Edit2: 是否可以使用数据结构TRIE来解决？

- secretstuff

1

较小的字符串可以重复使用吗？也就是说，由cat、dog、mice组合而成的"catdogdogmice"或"catdogcatmice"是否有效？此外，不使用一些较小的字符串是否合法？例如，能否用cat、dog、mice来构成"catdog"？ - Frerich Raabe

1

秘密文件，如果您能回答这些问题就太好了。这是一个有趣的问题，但答案因问题细节而异。 - Peter - Reinstate Monica

@FrerichRaabe 是的，较小的字符串可以重复使用多次。而且不使用一些字符串也是合法的。 - secretstuff

@PeterSchneider 不，这些字符串可以以任何顺序使用。 - secretstuff

@PeterSchneider 很抱歉:P，实际上我是一名高中学生，目前正在研究这样的基础问题（针对人类），并尝试弄清楚如何编码... - secretstuff

显示剩余3条评论

3个回答

1

如果一个字符串可以由较小的字符串组合而成，则至少其中一个较小的字符串必须是大字符串的前缀。对于每个匹配的前缀，从输入字符串中删除它并进行递归。如果没有前缀且剩余的输入字符串为空，则找到了一个解决方案。

- Frerich Raabe

1

这可以通过添加记忆化来进行优化 - 不要对已经检查过的后缀进行递归，这是我答案中的思路。 - Ivaylo Strandjev

1

同样是我的。我在这里所说的记忆化是为了避免在剥离相同部分后解决问题，想象一下这个测试 "somestringmanyotherletters..."，想象一下测试中包含 so、me 和 some 等其他字符串。你的方法将检查是否可以形成 "stringmanyotherletters..." 两次 - 一次是为了 so 和 me，另一次是为了 some。当你检查一个给定的后缀是否可以被形成时，你可以记忆化结果，避免重复做同样的工作。 - Ivaylo Strandjev

我认为你必须添加“最长”的匹配单词必须被选择，否则你可能会得到一些后面需要的短匹配。 - Peter - Reinstate Monica

正确，如果仅需要像OP中“检查是否”一样的“Yes”或“No”，则为每个匹配递归是不必要的。 - Peter - Reinstate Monica

@PeterSchneider：当然，如果你想知道是否有任何解决方案，你可以简单地终止递归（例如通过函数的返回值）。 - Frerich Raabe

显示剩余3条评论

0

Ivaylo Strandjev 的答案比我的答案更高效和更简洁。

如果你想让它变简单，可以使用一个字典（散列），查看在字符串从位置 0 到末尾的字符总和中是否能在字典中找到答案。如果找到了一个，就从当前位置 i 开始在字符串末尾重新开始计算字符总和。但是复杂度的最小值和最大值都是 n。

- Z. Clément

请注意，答案的顺序可能会改变。我认为如果效率不重要的话，这样说是可以的... - Ivaylo Strandjev

这就是为什么我谈论哈希，如果不是完全相同的单词，你就无法匹配它。如果不是匹配的单词，并且字典中的单词数量有限，那么避免冲突就很容易了。 - Z. Clément

这不是我想表达的意思 - 如果有多个单词是原始字符串的后缀，你将不得不探索几个选项，以确保该字符串不能被形成。最终你会得到一个与我提出的解决方案非常接近的解决方案。 - Ivaylo Strandjev

好的，我不理解那个.. 是的，事实上这就是为什么我注意到你的答案比我的更有效率和更干净。对于这个答案，我只是谈论了实现它的简单方法，而不是真正的效率问题。而且我们没有关于他想要使用哪种情况的细节，所以我给出了最简单的方法来根据他的示例和有限的词汇来完成它。 - Z. Clément

我明白您所说的不是效率问题，但我在这里所讨论的是准确性问题。以这个例子为例：somestring，单词分别是 so、some、ring 和 string。您提出的算法会做些什么呢？ - Ivaylo Strandjev

显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ivaylo Strandjev · Accepted Answer

注意：此解决方案假设您可以重复使用单词。

您可以使用动态规划方法来实现。将子问题定义为“初始字符串从位置i开始的后缀是否可以由给定的字符串组成”。DP是一维的，因此我将假设您将子问题结果存储在大小为n（初始字符串的大小）的数组dp中。在每个单元格中，存储一个标志 - 是否可能形成给定的后缀。

现在，要解决给定索引i的问题，您需要执行以下操作 - 遍历所有单词，并针对每个单词w_j，如果w_j是初始字符串后缀的前缀，则如果dp[i + len(w_j)]为1，则将dp[i]设置为1。

为了更容易理解，假设我们有字符串s₀s₀s₁...s_is_i+1...s_n。为计算dp[i]，请遍历所有单词。假设我们目前在单词w_j上，如果w_j不是s_is_i+1...s_n的前缀（即w_j[0]==s_i，w_j[1]==s_i+1等），则不执行任何操作。否则，请检查dp[i + strlen(w_j)]是否为一，如果是，则将dp[i]设置为1并停止对其他单词的迭代。

该方法的内存开销将是线性的，并且其计算复杂度将按照n * m * max_word_len的顺序进行，其中m为单词数，max_word_len为允许的最大单词长度。