Vấn đề ngắt từ

Trong đầu vào của bài toán này, một câu được đưa ra không có khoảng trắng, một từ điển khác cũng được cung cấp một số từ tiếng Anh hợp lệ. Chúng ta phải tìm ra những cách khả thi để ngắt câu trong từng từ điển riêng lẻ.

Chúng tôi sẽ cố gắng tìm kiếm từ bên trái của chuỗi để tìm một từ hợp lệ khi tìm thấy một từ hợp lệ, chúng tôi sẽ tìm kiếm các từ trong phần tiếp theo của chuỗi đó.

Đầu vào và Đầu ra

Input:
A set of valid words as dictionary, and a string where different words are placed without spaces.
Dictionary: {mobile, sam, sung, man, mango, icecream, and, go, i, love, ice, cream}
Given String: “ilovemangoicecream”
Output:
All possible ways to break the string into given words.
i love man go ice cream
i love man go icecream
i love mango ice cream
i love mango icecream

Thuật toán

wordBreak(string, n, result)

Đầu vào - Chuỗi cho trước, độ dài của chuỗi, các chuỗi được phân tách.

Đầu ra - Tách chuỗi bằng từ điển.

Begin
   for i := 0 to n, do
      subStr := substring of given string from (0..i)
      if subStr is in dictionary, then
         if i = n, then
            result := result + subStr
            display the result
            return
         wordBreak(substring from (i..n-i), n-i, result, subStr, ‘space’)
   done
End

Ví dụ

#include <iostream>
#define N 13
using namespace std;

string dictionary[N] = {"mobile","samsung","sam","sung","man","mango", "icecream","and",
                        "go","i","love","ice","cream"};

int isInDict(string word){    //check whether the word is in dictionary or not
   for (int i = 0; i < N; i++)
      if (dictionary[i].compare(word) == 0)
         return true;
   return false;
}

void wordBreak(string str, int n, string result) {
   for (int i=1; i<=n; i++) {
      string subStr = str.substr(0, i);       //get string from 0 to ith location of the string
      if (isInDict(subStr)) {       //if subStr is found in the dictionary
         if (i == n) {
            result += subStr; //add substring in the result.
            cout << result << endl;
            return;
         }
         wordBreak(str.substr(i, n-i), n-i, result + subStr + " ");    //otherwise break rest part
      }
   }
}

int main() {
   string str="iloveicecreamandmango";
   wordBreak(str, str.size(),"");
}

Đầu ra

i love man go ice cream
i love man go icecream
i love mango ice cream
i love mango icecream