ปัญหาการแตกคำ

ในการป้อนข้อมูลของปัญหานี้ ประโยคหนึ่งจะถูกกำหนดโดยไม่มีการเว้นวรรค และพจนานุกรมอีกฉบับมีคำศัพท์ภาษาอังกฤษที่ถูกต้องบางคำให้ด้วย เราต้องหาวิธีที่เป็นไปได้ในการทำลายประโยคในแต่ละคำในพจนานุกรม

เราจะพยายามค้นหาจากด้านซ้ายของสตริงเพื่อค้นหาคำที่ถูกต้องเมื่อพบคำที่ถูกต้อง เราจะค้นหาคำในส่วนถัดไปของสตริงนั้น

อินพุตและเอาต์พุต

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

อัลกอริทึม

wordBreak(string, n, result)

อินพุต - กำหนดสตริง ความยาวของสตริง สตริงที่แยกออก

ผลลัพธ์ - แยกสตริงโดยใช้พจนานุกรม

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

ตัวอย่าง

#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(),"");
}

ผลลัพธ์

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