मान लीजिए हमारे पास एक गैर-खाली स्ट्रिंग s और एक डिक्शनरी wordDict है। जिसमें गैर-खाली शब्दों की एक सूची है, यह निर्धारित करें कि s को एक या अधिक डिक्शनरी शब्दों के स्पेस-सेपरेटेड अनुक्रम में विभाजित किया जा सकता है या नहीं। हमें कुछ नियमों का पालन करना होगा -
- डिक्शनरी में वही शब्द विभाजन में कई बार पुनः उपयोग किया जा सकता है।
- हम मान सकते हैं कि डिक्शनरी में डुप्लिकेट शब्द नहीं हैं।
मान लीजिए स्ट्रिंग s = "applepenapple", और वर्ड डिक्शनरी ["apple", "pen"] जैसी है, तो आउटपुट true होगा क्योंकि स्ट्रिंग s को "apple pen apple" के रूप में विभाजित किया जा सकता है।
चरण देखें -
- n x n क्रम का एक मैट्रिक्स DP परिभाषित करें। n = स्ट्रिंग का आकार, और इसे false से इनिशियलाइज़ करें
- i के लिए 1 से s की लंबाई तक की रेंज में
- j के लिए 0 से s की लंबाई - i तक की रेंज में
- यदि सबस्ट्रिंग s[j से j + 1] डिक्शनरी में है, तो dp[j, j+i - 1] := True
- अन्यथा
- k के लिए j + 1 से j + i तक
- यदि dp[j, k - 1] और dp[k, j + i - 1], तो dp[j, j + i - 1] := True
- k के लिए j + 1 से j + i तक
- j के लिए 0 से s की लंबाई - i तक की रेंज में
- DP[0, s की लंबाई - 1] लौटाएं
उदाहरण (पायथन)
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
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
