Giả sử chúng ta có một chuỗi không rỗng s và một wordDict từ điển. Đó là chứa danh sách các từ không trống, xác định thời điểm có thể phân đoạn s thành một chuỗi được phân tách bằng dấu cách của một hoặc nhiều từ trong từ điển. Chúng tôi phải tuân theo một số quy tắc -
- Cùng một từ trong từ điển có thể được sử dụng lại nhiều lần trong phân đoạn.
- Chúng tôi có thể cho rằng từ điển không chứa các từ trùng lặp.
Giả sử chuỗi s =“applepenapple” và từ điển từ giống như [“apple”, “pen”], thì kết quả đầu ra sẽ là true vì chuỗi s có thể được phân đoạn là “apple pen apple”.
Hãy để chúng tôi xem các bước -
- Xác định một DP ma trận bậc n x n. n =kích thước của chuỗi và khởi tạo nó bằng false
- cho tôi trong phạm vi từ 1 đến độ dài là s
- cho j trong phạm vi từ 0 đến độ dài của s - i
- nếu chuỗi con s [j đến j + 1] trong từ điển, thì dp [j, j + i - 1]:=True
- nếu không thì
- cho k trong phạm vi j + 1 đến j + i
- nếu dp [j, k - 1] và dp [k, j + i - 1] thì dp [j, j + i - 1]:=True
- cho k trong phạm vi j + 1 đến j + i
- cho j trong phạm vi từ 0 đến độ dài của s - i
- trả về DP [0, độ dài s - 1]
Ví dụ (Python)
Hãy cùng chúng tôi xem cách 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): #print(s[j:j+i]) 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