मान लीजिए कि हमारे पास एक गैर-रिक्त स्ट्रिंग s और वर्डडिक्ट नामक एक शब्दकोष है, इस शब्दकोश में गैर-रिक्त शब्दों की एक सूची है, एक वाक्य बनाने के लिए s में रिक्त स्थान जोड़ें जहां प्रत्येक शब्द है एक वैध शब्दकोश शब्द। हमें ऐसे सभी संभावित वाक्यों को खोजना होगा। "एप्पलरेनकोट" और शब्दकोश ["ऐप", "सेब", "रेन", "कोट", "रेनकोट"]
हैइसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक मैप मेमो बनाएं
-
हल नामक एक विधि को परिभाषित करें, इसमें स्ट्रिंग और वर्डडिक्ट लगेगा
-
यदि s शून्य है, तो खाली सूची लौटाएं
-
अगर मेमो में है, तो -
-
वापसी मेमो[s]
-
-
एक सरणी रिट बनाएं
-
मेरे लिए 1 से लेकर s के आकार तक
-
यदि वर्ड डिक्ट में इंडेक्स 0 से i - 1 में s का सबस्ट्रिंग मौजूद है, तो
-
हल करने के लिए j के लिए (i से अंत तक s का सबस्ट्रिंग, wordDict)
-
p :=इंडेक्स 0 से i-1 में s का सबस्ट्रिंग, स्पेस और j के साथ संयोजित करें, फिर बाएँ और दाएँ से अतिरिक्त स्थान साफ़ करें -
-
रिट में p डालें
-
-
-
ज्ञापन [एस] :=सेवानिवृत्त
-
वापसी मेमो[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']