ปัญหาการแบ่งคำ (Word Break Problem)

บทนำ

ได้รับประโยคโดยไม่มีช่องว่าง และพจนานุกรมคำที่ถูกต้อง ต้องการหาวิธีแบ่งประโยคเป็นคำในพจนานุกรมได้ทั้งหมด

วิธีแก้: ค้นหาจากซ้ายไปขวา หาคำที่ถูกต้อง แล้วค่อยค้นหาต่อในส่วนที่เหลือ

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

Input: Dictionary: {mobile, sam, sung, man, mango, icecream, and, go, i, love, ice, cream}
       String: "ilovemangoicecream"
Output: ทุกวิธีแบ่งคำ:
        i love man go ice cream
        i love man go icecream
        i love mango ice cream
        i love mango icecream

อัลกอริทึม

wordBreak(string, n, result)

Input: สตริงที่กำหนด, ความยาวสตริง, สตริงที่แบ่งแล้ว
Output: แยกสตริงโดยใช้พจนานุกรม

Begin
    for i := 0 ถึง n do
        subStr := substring จาก (0..i)
        if subStr อยู่ในพจนานุกรม then
            if i = n then
                result := result + subStr
                แสดง result
                return
            wordBreak(substring จาก (i..n-i), n-i, result + subStr + " ")
    done
End

ตัวอย่างโค้ด (C++)

#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){
    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);
        if (isInDict(subStr)) {
            if (i == n) {
                result += subStr;
                cout << result << endl;
                return;
            }
            wordBreak(str.substr(i, n-i), n-i, result + subStr + " ");
        }
    }
}

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