Ngắt từ trong Python

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
• 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