ধরুন আমাদের একটি অ-খালি স্ট্রিং এবং একটি অভিধান wordDict আছে৷ এটি অ-খালি শব্দের একটি তালিকা ধারণ করে, s কে কখন এক বা একাধিক অভিধান শব্দের একটি স্থান-বিচ্ছিন্ন ক্রমানুসারে ভাগ করা যেতে পারে তা নির্ধারণ করুন। আমাদের কিছু নিয়ম মেনে চলতে হবে -
- অভিধানে একই শব্দ একাধিকবার সেগমেন্টেশনে ব্যবহার করা যেতে পারে।
- আমরা ধরে নিতে পারি যে অভিধানে সদৃশ শব্দ নেই।
ধরুন স্ট্রিং s =“applepenapple”, এবং শব্দ অভিধানটি [“apple”, “pen”] এর মত, তাহলে আউটপুট সত্য হবে কারণ স্ট্রিং s কে “apple pen apple” হিসাবে ভাগ করা যেতে পারে।
আসুন ধাপগুলো দেখি -
- ক্রম n x n এর একটি ম্যাট্রিক্স ডিপি সংজ্ঞায়িত করুন। n =স্ট্রিংয়ের আকার, এবং এটিকে মিথ্যা দিয়ে শুরু করুন
- আমি 1 থেকে s
- এর দৈর্ঘ্যের মধ্যে
- j-এর জন্য 0 থেকে s-এর দৈর্ঘ্যের মধ্যে – i
- যদি অভিধানে সাবস্ট্রিং s[j থেকে j + 1] হয়, তাহলে dp[j, j+i - 1] :=True
- অন্যথায়
- j + 1 থেকে j + i
- যদি dp[j, k - 1] এবং dp[k, j + i – 1] হয়, তাহলে dp[j, j + i – 1] :=সত্য
- পরিসরে k-এর জন্য
- j-এর জন্য 0 থেকে s-এর দৈর্ঘ্যের মধ্যে – i
উদাহরণ(পাইথন)
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
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"])) ইনপুট
"applepenapple" ["apple", "pen"]
আউটপুট
true
