Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

पायथन में सबसे लंबे पैलिंड्रोमिक सबस्ट्रिंग की लंबाई ढूंढने का प्रोग्राम


मान लीजिए हमारे पास एक स्ट्रिंग S है। हमें S में सबसे लंबे पैलिंड्रोमिक सबस्ट्रिंग की लंबाई ढूंढनी है। हम मान रहे हैं कि स्ट्रिंग S की लंबाई 1000 है। उदाहरण के लिए, यदि स्ट्रिंग "BABAC" है, तो सबसे लंबा पैलिंड्रोमिक सबस्ट्रिंग "BAB" है और इसकी लंबाई 3 है।

समाधान दृष्टिकोण (डायनामिक प्रोग्रामिंग)

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

  1. स्ट्रिंग की लंबाई के बराबर क्रम का एक वर्ग मैट्रिक्स परिभाषित करें और इसे False से भरें।
  2. मुख्य विकर्ण के एलिमेंट्स को True सेट करें, यानी DP[i][i] = True सभी i के लिए 0 से length-1 तक।
  3. start = 0 और max_length = 1 आरंभ करें।
  4. सबस्ट्रिंग की लंबाई l के लिए 2 से length of S + 1 तक लूप चलाएं:
    • प्रारंभिक इंडेक्स i के लिए 0 से length of S - l + 1 तक लूप चलाएं।
    • end = i + l की गणना करें।
    • यदि l == 2 है:
      • यदि S[i] == S[end-1], तो DP[i][end-1] = True, max_length = l, और start = i सेट करें।
    • अन्यथा (l > 2):
      • यदि S[i] == S[end-1] और DP[i+1][end-2] True है, तो DP[i][end-1] = True, max_length = l, और start = i सेट करें।
  5. max_length लौटाएं।

पायथन कार्यान्वयन

class Solution(object):
def solve(self, s):
dp = [[False for _ in range(len(s))] for _ in range(len(s))]
for i in range(len(s)):
dp[i][i] = True
max_length = 1
start = 0
for l in range(2, len(s)+1):
for i in range(len(s)-l+1):
end = i + l
if l == 2:
if s[i] == s[end-1]:
dp[i][end-1] = True
max_length = l
start = i
else:
if s[i] == s[end-1] and dp[i+1][end-2]:
dp[i][end-1] = True
max_length = l
start = i
return max_length

ob = Solution()
print(ob.solve('BABAC'))

इनपुट

"ABBABBC"

आउटपुट

5
  1. - पायथन में सबसे लंबी एनाग्राम उप-अनुक्रम की लंबाई खोजने का प्रोग्राम

    मान लीजिए हमारे पास दो लोअरकेस स्ट्रिंग्स S और T हैं, हमें सबसे लंबी एनाग्राम उप-अनुक्रम की लंबाई ढूंढनी है। उदाहरण के लिए, यदि इनपुट S = helloworld, T = hellorld है, तो आउटपुट 8 होगा। इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे: c := एक नया मैप, d := एक नया मैप। i को 0 से len(a) - 1 तक लूप म

  1. - पायथन में सबसे लंबे संतुलित उप-अनुक्रम की लंबाई खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक स्ट्रिंग s है जिसमें ब्रैकेट्स ( और ) हैं, हमें संतुलित ब्रैकेट्स के सबसे लंबे उप-अनुक्रम की लंबाई ढूंढनी है। उदाहरण के लिए, यदि इनपुट s = ())(()( है, तो आउटपुट 4 होगा, क्योंकि हम ()() जैसा उप-अनुक्रम ले सकते हैं। इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे: res := 0, n

  1. - पायथन में सबसे लंबा पालिंड्रोमिक सबस्ट्रिंग

    मान लीजिए हमारे पास एक स्ट्रिंग S है। हमें S में सबसे लंबा पालिंड्रोमिक सबस्ट्रिंग ढूंढना है। हम मान रहे हैं कि स्ट्रिंग S की लंबाई 1000 है। इसलिए यदि स्ट्रिंग BABAC है, तो सबसे लंबा पालिंड्रोमिक सबस्ट्रिंग BAB है। इसे हल करने के लिए, हम इन चरणों का पालन करेंगे: स्ट्रिंग की लंबाई के समान क्रम का