Bài toán Tách từ (Word Break Problem)

Giới thiệu

Cho một câu không có dấu cách và một từ điển các từ tiếng Anh hợp lệ. Tìm tất cả các cách tách câu thành các từ trong từ điển.

Duyệt từ trái sang phải: khi tìm thấy từ hợp lệ, đệ quy tách phần còn lại.

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

Đầu vào: Từ điển: {mobile, sam, sung, man, mango, icecream, and, go, i, love, ice, cream}
Chuỗi: "ilovemangoicecream"
Đầu ra: Tất cả cách tách:
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 chuỗi, chuỗi kết quả tách.

Đầu ra: Tách chuỗi dùng từ điển.

Begin
  với i := 0 đến n làm:
    subStr := chuỗi con từ (0..i)
    nếu subStr trong từ điển thì
      nếu i = n thì
        result := result + subStr
        hiển thị result
        return
      wordBreak(chuỗi con từ (i..n-i), n-i, result + subStr + ' ')
    done
End

Ví dụ (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(), "");
}

Kết quả đầu ra

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