एक स्ट्रिंग की जाँच करने के लिए प्रोग्राम को तीन पैलिंड्रोम में विभाजित किया जा सकता है या पायथन में नहीं

मान लीजिए कि हमारे पास एक स्ट्रिंग s है। हमें यह जांचना होगा कि क्या हम s को तीन पैलिंड्रोमिक सबस्ट्रिंग में विभाजित कर सकते हैं या नहीं।

इसलिए, यदि इनपुट s ="levelpopracecar" जैसा है, तो आउटपुट सही होगा क्योंकि हम इसे "स्तर", "पॉप", "रेसकार" की तरह विभाजित कर सकते हैं, सभी पैलिंड्रोम हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=s का आकार

• dp :=क्रम n x n का एक मैट्रिक्स और असत्य से भरें

• n-1 से 0 की श्रेणी में i के लिए, 1 से घटाएं, करें

  • j के लिए 0 से n-1 की सीमा में, करें

    • अगर मैं>=जे, तो

      • डीपी [i, जे]:=सच

    • अन्यथा जब s[i] s[j] के समान है, तब

      • डीपी [i, जे]:=डीपी [i+1, j-1]

  • 1 से n-1 की श्रेणी में i के लिए, करें

    • i+1 से n-1 की श्रेणी में j के लिए, करें

      • अगर dp[0, i-1] और dp[i, j-1] और dp[j, n-1] सभी सही हैं, तो

        • सही लौटें

• झूठी वापसी

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें

def solve(s):
   n = len(s)

   dp = [[False] * n for _ in range(n)]
   for i in range(n-1, -1, -1):
      for j in range(n):
         if i >= j:
            dp[i][j] = True
         elif s[i] == s[j]:
            dp[i][j] = dp[i+1][j-1]
   for i in range(1, n):
      for j in range(i+1, n):
         if dp[0][i-1] and dp[i][j-1] and dp[j][n-1]:
            return True
   return False

s = "levelpopracecar"
print(solve(s))

इनपुट

"levelpopracecar"

आउटपुट

True