我正在尝试解决this问题。问题如下
给定一个输入字符串和一个单词词典,请确定输入字符串是否可以分割成以空格分隔的词典单词序列。
字典是一个字符串数组。
我的方法是在以下递归函数中存储递归调用的结果。输出很好,但我发现从未使用过存储的结果。
我的解决方案通过了测试用例,希望是正确的,但是如果我知道是否使用DP,那将是很棒的。
代码是:
#include <iostream>
#include <string.h>
using namespace std;
int r[100][100] = {0}; //To Store the calculated values
bool searchWord(char q[], char D[][20], int start, int end) {
cout << "In Search Word Loop with " << start << " " << end << endl;
char temp[end - start + 1];
int j = 0;
for (int i = start; i <= end ; ++i) {
//cout << "Looping i " << i << endl;
temp[j] = q[i];
j++;
}
// cout << "For Word " << temp << endl;
for (int i = 0; i < 12; ++i) {
// cout << "Comparing with " << D[i] << endl;
if (!strcmp(temp, D[i])) {
cout << "Found Word" << temp << " " << D[i] << endl;
return 1;
}
}
return 0;
}
bool searchSentence(char q[], char D[][20], int qstart, int qend) {
cout << "In Search Sentence Loop" << endl;
if (r[qstart][qend] != 0) {
cout << "DP Helped!!!" << endl;
return 1;
}
if (qstart == qend) {
if (searchWord(q, D, qstart, qstart))
return 1;
else return 0;
}
if (qstart > qend) return 1;
int i;
for (i = qstart; i <= qend; i++) {
if (searchWord(q, D, qstart, i)) {
r[i + 1][qend] = searchSentence(q, D, i + 1, qend);
if (r[i + 1][qend] == 1) return 1;
}
}
return 0;
}
int main() {
char D[20][20] = { "i", "like", "sam", "sung", "samsung", "mobile", "ice", "cream", "icecream", "man", "go", "mango"};
char q[100] = "samsungmango";
int index = 0; char ch;
ch = q[0];
while (ch != '\0') {
index++;
ch = q[index];
}
if (searchSentence(q, D, 0, index - 1))
cout << "Yes" << endl;
else cout << "No" << endl;
}
最佳答案
您的代码实际上是错误的。要使代码失败,请尝试输入“likeman”
请注意,函数searchSentence
可能有两个不同的返回值,0或1。因此,如果将r
数组初始化为0,则不能保证r[x][y] = 0
时它是新状态。用一些不可能的值(例如-1或2)初始化r数组,然后再次测试。现在,您可以轻松地确认是否为r[qbegin][qend] != -1
,那么已经检查了此状态,因此您可以从此处返回r[qbegin][qend]
更新的代码:
#include <iostream>
#include <string.h>
using namespace std;
int r[100][100]; //To Store the calculated values
bool searchWord(char q[], char D[][20], int start, int end)
{
cout << "In Search Word Loop with " << start << " " << end << endl;
char temp[end - start + 1];
int j = 0;
for (int i = start; i <= end ; ++i)
{
//cout << "Looping i " << i << endl;
temp[j] = q[i];
j++;
}
temp[j] = '\0';
//cout << "For Word " << temp << endl;
for (int i = 0; i < 12; ++i)
{
// cout << "Comparing with " << D[i] << endl;
if (!strcmp(temp, D[i]))
{
cout << "Found Word" << temp << " " << D[i] << endl;
return 1;
}
}
return 0;
}
bool searchSentence(char q[], char D[][20], int qstart, int qend)
{
cout << "In Search Sentence Loop" << endl;
if (r[qstart][qend] != -1)
{
cout << "DP Helped!!!" << endl;
return r[qstart][qend];
}
if (qstart == qend)
{
if (searchWord(q, D, qstart, qstart))
return 1;
else return 0;
}
if (qstart > qend) return 1;
int i;
for (i = qstart; i <= qend; i++)
{
if (searchWord(q, D, qstart, i))
{
r[i + 1][qend] = searchSentence(q, D, i + 1, qend);
if (r[i + 1][qend] == 1) return 1;
}
}
return 0;
}
int main()
{
char D[20][20] = { "i", "like", "sam", "sung", "samsung", "mobile", "ice", "cream", "icecream", "man", "go", "mango"};
char q[100] = "ilike";
int index = 0; char ch;
ch = q[0];
memset(r, -1, sizeof(r));
while (ch != '\0')
{
index++;
ch = q[index];
}
if (searchSentence(q, D, 0, index - 1))
cout << "Yes" << endl;
else cout << "No" << endl;
}
P.S:有一些多余的代码行,但是我没有更改它们,我在函数
searchWord
的字符数组temp的末尾添加了一个空字符关于c++ - 动态编程-分词,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/25168061/