Dynamic Programming - Word Break

问题:

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;
}

回答1:

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

回答2:

Is recursion mandatory? I see, iterative DP-solution is easiest and compact:

#include <stdio.h>
#include <string.h>

int main() {
  const char *D[] = { "i", "like", "sam", "sung", "samsung", "mobile", "ice", "cream", "icecream", "man", "go", "mango", NULL};
  const char q[] = "samsungmango";
  char dp[100];
  short d_len[20];
  memset(dp, 0, sizeof(dp));
  dp[0] = 1; // 0 element is always reacheable
  int i, j;
  // compute dict string lengths
  for(i = 0; D[i]; i++)
      d_len[i] = strlen(D[i]);

  // Compute splits using DP array
  for(i = 0; q[i] != 0; i++)
      if(dp[i])  // this index is reacheable
          for(j = 0; D[j]; j++) // try to make next reacheable indexes
              if(strncmp(&q[i], D[j], d_len[j]) == 0)
                  dp[i + d_len[j]] = 1; // That position is reacheable, too

  // if EOLN(q) is reached, then yes
  printf("Answer is %s\n", dp[i]? "YES" : "NO");

} // main