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