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

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

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

हल करने के चरण

1. n := len(s)
2. dp := क्रम n x n का मैट्रिक्स और False से भरें
3. i को n-1 से 0 तक घटाते हुए लूप चलाएं:
   • j को 0 से n - 1 तक लूप चलाएं:
     • यदि i >= j, तो dp[i][j] := True
     • अन्यथा यदि s[i] == s[j], तो dp[i][j] := dp[i+1][j-1]
4. i को 1 से n - 1 तक लूप चलाएं:
   • j को i+1 से n - 1 तक लूप चलाएं:
     • यदि dp[0][i-1] और dp[i][j-1] और dp[j][n-1] सभी True हैं, तो True वापस करें।
5. False वापस करें।

उदाहरण

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

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