动态规划 - 字歇 [英] Dynamic Programming - Word Break
问题描述
我试图解决这的问题.The问题如下
给定一个输入字符串和单词的字典，看看是否输入的字符串可以分割成字典单词空格分隔的序列。
词典是一个字符串数组。
我的做法是下面的递归FN与存储递归调用的结果。输出是不错，但我看到所存储的结果是从未使用过。 我的解决方案是希望正确的，因为它通过测试cases.But我将是巨大的，如果我知道DP是否被使用。
在code是：
的#include＆LT;的iostream＆GT;
＃包括＆LT; string.h中＆GT;
使用名字空间std;
INT R [100] [100] = {0}; //存储计算的值
布尔searchWord（字符Q []，焦炭D [] [20]，诠释开始，诠释完）{
COUT＆LT;＆LT; 在搜索词与河套＆LT;＆LT;启动＆LT;＆LT; ＆LT;＆LT;结束＆LT;＆LT; ENDL;
焦炭温度[结束 - 开始+ 1];
INT J = 0;
的for（int i =启动; I＆LT; =结束; ++ I）{
// cout的＆LT;＆LT; 我循环＆LT;＆LT; I＆LT;＆LT; ENDL;
温度[J] = Q [我]
J ++;
}
// cout的＆LT;＆LT; 对于Word＆LT;＆LT;温度＆LT;＆LT; ENDL;
的for（int i = 0; I＆LT; 12; ++ I）{
// cout的＆LT;＆LT; ＆LT与比较;＆LT; D [1] - ;＆其中; ENDL;
如果（！的strcmp（温度，D [I]））{
COUT＆LT;＆LT; 发现字＆LT;＆LT;温度＆LT;＆LT; ＆LT;＆LT; D [1] - ;＆其中; ENDL;
返回1;
}
}
返回0;
}
布尔searchSentence（字符Q []，焦炭D [] [20]，INT QSTART，诠释QEND）{
COUT＆LT;＆LT; 在搜索句循环＆LT;＆LT; ENDL;
如果（R [QSTART] [QEND]！= 0）{
COUT＆LT;＆LT; DP帮助了！ ＆LT;＆LT; ENDL;
返回1;
}
如果（QSTART == QEND）{
如果（searchWord（Q，D，QSTART，QSTART））
返回1;
否则返回0;
}
如果（QSTART＆GT; QEND）返回1;
INT I;
对于（i = QSTART; I＆LT; = QEND;我++）{
如果（searchWord（Q，D，QSTART，I））{
ř[I + 1] [QEND] = searchSentence（Q，D，i + 1的，QEND）;
如果（R [I + 1] [QEND] == 1）返回1;
}
}
返回0;
}
诠释的main（）{
字符D [20] [20] = {我，喜欢，山姆，宋史，三星，手机，冰，奶油，冰淇淋，人， 走出去，芒果};
焦炭Q [100] =samsungmango;
INT索引= 0;焦CH;
CH = Q [0];
而（CH！='\ 0'）{
指数++;
CH = Q [指数]
}
如果（searchSentence（Q，D，0，指数 - 1））
COUT＆LT;＆LT; 是的＆LT;＆LT; ENDL;
否则COUT＆LT;＆LT; 无＆其中;＆其中; ENDL;
}
您code其实是错误的。要失败的code，尝试输入如likeman
请注意，有两个不同的返回值可以从功能 searchSentence 0或1。因此，如果你初始化研究阵列0不能保证它是一个新的状态时，研究[X] [Y] = 0 。初始化 - [R数组像-1或2对这一计划并再次测试一些不可能的价值。现在，你可以很容易地确认，如果研究[qbegin] [QEND]！= -1 那么这个国家已经被检查，所以你可以返回研究[ qbegin] [QEND] 从这里
更新code：
的#include＆LT;的iostream＆GT;
＃包括＆LT; string.h中＆GT;
使用名字空间std;
INT R [100] [100] //存储计算的值
布尔searchWord（字符Q []，焦炭D [] [20]，诠释开始，诠释完）
{
COUT＆LT;＆LT; 在搜索词与河套＆LT;＆LT;启动＆LT;＆LT; ＆LT;＆LT;结束＆LT;＆LT; ENDL;
焦炭温度[结束 - 开始+ 1];
INT J = 0;
的for（int i =启动; I＆LT; =结束; ++ I）
{
// cout的＆LT;＆LT; 我循环＆LT;＆LT; I＆LT;＆LT; ENDL;
温度[J] = Q [我]
J ++;
}
温度[J] ='\ 0';
// cout的＆LT;＆LT; 对于Word＆LT;＆LT;温度＆LT;＆LT; ENDL;
的for（int i = 0; I＆LT; 12; ++ I）
{
// cout的＆LT;＆LT; ＆LT与比较;＆LT; D [1] - ;＆其中; ENDL;
如果（！的strcmp（温度，D [I]））
{
COUT＆LT;＆LT; 发现字＆LT;＆LT;温度＆LT;＆LT; ＆LT;＆LT; D [1] - ;＆其中; ENDL;
返回1;
}
}
返回0;
}
布尔searchSentence（字符Q []，焦炭D [] [20]，INT QSTART，INT QEND）
{
COUT＆LT;＆LT; 在搜索句循环＆LT;＆LT; ENDL;
如果（R [QSTART] [QEND]！= -1）
{
COUT＆LT;＆LT; DP帮助了！ ＆LT;＆LT; ENDL;
回报 - [R [QSTART] [QEND]
}
如果（QSTART == QEND）
{
如果（searchWord（Q，D，QSTART，QSTART））
返回1;
否则返回0;
}
如果（QSTART＆GT; QEND）返回1;
INT I;
对于（i = QSTART; I＆LT; = QEND;我++）
{
如果（searchWord（Q，D，QSTART，I））
{
ř[I + 1] [QEND] = searchSentence（Q，D，i + 1的，QEND）;
如果（R [I + 1] [QEND] == 1）返回1;
}
}
返回0;
}
诠释的main（）
{
字符D [20] [20] = {我，喜欢，山姆，宋史，三星，手机，冰，奶油，冰淇淋，人， 走出去，芒果};
焦炭Q [100] =ILIKE;
INT索引= 0;焦CH;
CH = Q [0];
memset的（R，-1，sizeof的（R））;
而（CH！='\ 0'）
{
指数++;
CH = Q [指数]
}
如果（searchSentence（Q，D，0，指数 - 1））
COUT＆LT;＆LT; 是的＆LT;＆LT; ENDL;
否则COUT＆LT;＆LT; 无＆其中;＆其中; ENDL;
}
PS：这里是codeS一些多余的线条，但我并没有改变他们，我在功能上的字符数组临时的末尾添加一个空字符 searchWord
I am trying to solve this Problem.The question is as follows
Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words.
Dictionary is an array of strings.
My Approach is the following recursive fn with storing of the results of recursive calls. The output is fine but I see that the stored result is never used. My solution is hopefully correct as it passed the test cases.But I would be great if I know whether DP is used.
The code is:
#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;
}
Your code is actually wrong. To fail your code, try input like "likeman"
Note that there are two different return values possible from function searchSentence, 0 or 1. So if you initialize the r array with 0 there's no guarantee it's a new state when r[x][y] = 0. Initialize r array with some impossible value like -1 or 2 for this program and test again. Now you can easily confirm that if r[qbegin][qend] != -1 then this state has already been checked so you can return r[qbegin][qend] from here
Updated code :
#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 : There are some redundant lines of codes but I didn't change them and I added a null character in the end of the character array temp in function searchWord
这篇关于动态规划 - 字歇的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
