पायथन में वर्ड ब्रेक

मान लीजिए कि हमारे पास एक गैर-रिक्त स्ट्रिंग s और एक शब्दकोष wordDict है। इसमें गैर-रिक्त शब्दों की एक सूची है, यह निर्धारित करें कि कब s को एक या अधिक शब्दकोष शब्दों के स्थान-पृथक अनुक्रम में विभाजित किया जा सकता है। हमें कुछ नियमों का पालन करना होगा -

• शब्दकोश में एक ही शब्द का विभाजन में कई बार पुन:उपयोग किया जा सकता है।
• हम मान सकते हैं कि शब्दकोश में डुप्लिकेट शब्द नहीं हैं।

मान लीजिए कि स्ट्रिंग s ="applepenapple", और शब्द शब्दकोष ["apple", "pen"] जैसा है, तो आउटपुट सही होगा क्योंकि स्ट्रिंग s को "ऐप्पल पेन ऐप्पल" के रूप में विभाजित किया जा सकता है।

आइए चरणों को देखें -

• क्रम n x n के एक मैट्रिक्स DP को परिभाषित करें। n =स्ट्रिंग का आकार, और इसे असत्य से प्रारंभ करें
• 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
• रिटर्न 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