动态编程-分词

小编典典

动态编程-分词

algorithm

我正在尝试解决这个问题。问题如下：
给定一个输入字符串和一个单词词典，找出是否可以将输入字符串分割成以空格分隔的词典单词序列。

字典是一个字符串数组。

我的方法是在以下递归函数中存储递归调用的结果。输出很好，但我发现从未使用过存储的结果。我的解决方案通过了测试用例，希望是正确的，但是如果我知道是否使用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;
}

阅读 230

2020-07-28

共1个答案

小编典典

您的代码实际上是错误的。要使代码失败，请尝试输入“ likeman”

请注意，函数searchSentence0或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;
}

PS：有一些多余的代码行，但是我没有更改它们，而是在函数的字符数组temp的末尾添加了一个空字符 searchWord

2020-07-28