Word Break (Ngắt từ) trong Python

Giả sử chúng ta có một chuỗi không rỗng s và một từ điển wordDict chứa danh sách các từ không rỗng. Xác định xem s có thể được phân đoạn thành chuỗi các từ trong từ điển cách nhau bởi dấu cách. Các quy tắc:

• Cùng một từ trong từ điển có thể được sử dụng lại nhiều lần.
• Giả định từ điển không chứa từ trùng lặp.

Ví dụ, chuỗi s = "applepenapple", từ điển ["apple", "pen"], đầu ra là true vì chuỗi có thể phân đoạn thành "apple pen apple".

Các bước thực hiện

• Định nghĩa ma trận DP cỡ n x n, n = độ dài chuỗi, khởi tạo bằng false.
• Với i từ 1 đến độ dài s:
  • Với j từ 0 đến độ dài s - i:
    • Nếu chuỗi con s[j:j+i] trong từ điển, thì dp[j][j+i-1] := True.
    • Ngược lại:
      • Với k từ j+1 đến j+i:
        • Nếu dp[j][k-1] và dp[k][j+i-1], thì dp[j][j+i-1] := True.
• Trả về DP[0][len(s)-1].

Ví dụ (Python)

Xem triển khai sau để hiểu rõ hơn:

class Solution(object):
    def wordBreak(self, s, wordDict):
        dp = [[False for i in range(len(s))] for x in range(len(s))]
        for i in range(1, len(s)+1):
            for j in range(len(s)-i+1):
                if s[j:j+i] in wordDict:
                    dp[j][j+i-1] = True
                else:
                    for k in range(j+1, j+i):
                        if dp[j][k-1] and dp[k][j+i-1]:
                            dp[j][j+i-1] = True
        return dp[0][len(s)-1]

ob1 = Solution()
print(ob1.wordBreak("applepenapple", ["apple", "pen"]))

Đầu vào

"applepenapple" ["apple", "pen"]

Đầu ra

true