ধরুন একটি নন-এম্পটি স্ট্রিং s এবং একটি ডিকশনারি wordDict আছে যেটে নন-এম্পटी শব্দের তালিকা রয়েছে। s-এ স্পেস যোগ করে এমন বাক্য তৈরি করতে হবে যাতে প্রতিটি শব্দ wordDict-এ থাকে। আমাদের এমন সব সম্ভাব্য বাক্য খুঁজে বের করতে হবে।
সমাধানের ধাপগুলো −
- একটি memo ম্যাপ তৈরি করুন
- solve মেথড সংজ্ঞায়িত করুন যা string এবং wordDict নেবে
- যদি s null হয় তবে খালি লিস্ট রিটার্ন করুন
- যদি s memo-তে থাকে তবে memo[s] রিটার্ন করুন
- ret অ্যারে তৈরি করুন
- i = 1 থেকে len(s) পর্যন্ত − যদি s[:i] wordDict-এ থাকে তবে s[i:] এর জন্য solve কল করে প্রতিটি j এর সাথে s[:i] + " " + j করুন এবং ret-এ যোগ করুন
- memo[s] := ret; memo[s] রিটার্ন করুন
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন −
class Solution(object):
def wordBreak(self, s, wordDict):
self.memo = {}
wordDict = set(wordDict)
return self.solve(s,wordDict)
def solve(self,s, wordDict):
if not s:
return ['']
if s in self.memo:
return self.memo[s]
ret = []
for i in range(1,len(s)+1):
if s[:i] in wordDict:
for j in self.solve(s[i:],wordDict):
ret.append((s[:i] + " " + j).strip())
self.memo[s] = ret
return self.memo[s]
ob = Solution()
print(ob.wordBreak("appleraincoat",["app","apple","rain","coat","rain coat"]))
ইনপুট
"appleraincoat" ["app","apple","rain","coat","raincoat"]
আউটপুট
['apple rain coat', 'apple raincoat']
