পাইথনে শব্দ বিরতি II

ধরুন আমাদের কাছে একটি অ-খালি স্ট্রিং s এবং wordDict নামে একটি অভিধান রয়েছে, এই অভিধানে খালি নয় এমন শব্দগুলির একটি তালিকা রয়েছে, একটি বাক্য গঠন করতে s-এ স্পেস যোগ করুন যেখানে প্রতিটি শব্দ একটি বৈধ অভিধান শব্দ। আমাদের এমন সব সম্ভাব্য বাক্য খুঁজে বের করতে হবে। "appleraincoat" এবং অভিধান হল [“app”, “apple”, “rain”, “coat”, “raincoat”]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি মানচিত্র মেমো তৈরি করুন

• সমাধান নামে একটি পদ্ধতি নির্ধারণ করুন, এটি স্ট্রিং এবং ওয়ার্ডডিক্ট

  নেবে

• যদি s শূন্য হয়, তাহলে খালি তালিকা ফেরত দিন

• যদি মেমোতে থাকে, তাহলে -

  • ফেরত মেমো[গুলি]

• একটি অ্যারে ret তৈরি করুন

• আমি 1 থেকে s আকারের সীমার মধ্যে

  • যদি wordDict-এ সূচক 0 থেকে i – 1 পর্যন্ত s-এর সাবস্ট্রিং থাকে, তাহলে

    • সমাধানে j এর জন্য (i থেকে শেষ পর্যন্ত s এর সাবস্ট্রিং, wordDict)

    • p :=ইনডেক্স 0 থেকে i – 1 পর্যন্ত s এর সাবস্ট্রিং, স্পেস এবং j দিয়ে সংযুক্ত করুন, তারপর বাম এবং ডান থেকে অতিরিক্ত জায়গা খালি করুন −

    • ret এ p ঢোকান

• মেমো[গুলি] :=ret

• ফেরত মেমো[গুলি]

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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']