पैलिंड्रोम विभाजन II
किसी स्ट्रिंग को पैलिंड्रोमों में विभाजित करने के लिए आवश्यक न्यूनतम कट खोजने हेतु पहले से बनाई गई पैलिंड्रोम तालिका को 1D DP के साथ मिलाइए।
पैलिंड्रोम विभाजन II, CoddyKit पर DSA Interview Prep का एक निःशुल्क पाठ है। यह 4 में से 3वाँ पाठ है। इस अध्ययन पथ के 3 तक कोई भी पाठ पूरा पढ़ना निःशुल्क है — इसके बाद CoddyKit PRO हर पाठ अनलॉक करता है, साथ ही अंतर्निर्मित कोड संपादक और चौबीसों घंटे एआई शिक्षक के साथ व्यावहारिक अभ्यास भी उपलब्ध कराता है। यह DSA Interview Prep सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। DSA Interview Prep पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
समस्या: विभाजन के लिए न्यूनतम कट
पैलिंड्रोम विभाजन II में पूछा जाता है: दी गई स्ट्रिंग s के लिए कट की न्यूनतम संख्या ज्ञात करें, ताकि विभाजन में आने वाली हर उपस्ट्रिंग एक पैलिंड्रोम हो। 'aab' के लिए एक कट से ['aa', 'b'] मिलता है, इसलिए उत्तर 1 है। 'a' के लिए उत्तर 0 है, क्योंकि वह पहले से ही एक पैलिंड्रोम है। इस समस्या में DP के दो चरण हैं: पहले यह पूर्व-गणना करना कि कौन-सी उपस्ट्रिंग पैलिंड्रोम हैं, फिर न्यूनतम कट ज्ञात करने के लिए 1D DP का उपयोग करना।
चरण 1: पैलिंड्रोम तालिका की पूर्व-गणना
सबसे पहले अंतराल DP का उपयोग करके s[i..j] के पैलिंड्रोम होने पर is_pal[i][j] = True बनाएँ। इसमें O(n²) समय और O(n²) स्थान लगता है। वैकल्पिक रूप से, केन्द्र के चारों ओर विस्तार करके यही तालिका O(n²) समय में भरी जा सकती है। हमें इस तालिका की आवश्यकता इसलिए है क्योंकि 1D कट DP बार-बार is_pal[i][j] को जाँचेगा — पहले से गणना करने से कट DP के लूप के भीतर पैलिंड्रोम की जाँच दोबारा नहीं करनी पड़ती।
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
print(build_palindrome_table('aab'))चरण 2: 1D कट DP की तैयारी
cuts[i] को s[0..i] के विभाजन के लिए आवश्यक न्यूनतम कट के रूप में परिभाषित करें। यदि s[0..i] स्वयं एक पैलिंड्रोम है, तो cuts[i] = 0 होगा। अन्यथा हर विभाजन आज़माएँ: 0 से i-1 तक प्रत्येक j के लिए, यदि s[j+1..i] एक पैलिंड्रोम है, तो cuts[i] = min(cuts[i], cuts[j] + 1) करें। हमारा प्रश्न है: यदि अंतिम विभाजन-खंड s[j+1..i] हो तो क्या होगा? तब उपसर्ग के लिए cuts[j] कट और उसके बाद 1 अतिरिक्त कट चाहिए।
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = [float('inf')] * n
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0 # entire prefix is a palindrome
else:
for j in range(i):
if is_pal[j+1][i]:
cuts[i] = min(cuts[i], cuts[j] + 1)
return cuts[n-1]पूर्ण समाधान और क्रमिक विवेचन
आइए 'aab' का क्रमवार विवेचन करें। पैलिंड्रोम तालिका: is_pal[0][0]='a'=T, is_pal[1][1]='a'=T, is_pal[2][2]='b'=T, is_pal[0][1]='aa'=T, is_pal[1][2]='ab'=F, is_pal[0][2]='aab'=F। कट: cuts[0]=0 ('a' एक पैलिंड्रोम है), cuts[1]=0 ('aa' एक पैलिंड्रोम है), cuts[2]: 'aab' पैलिंड्रोम नहीं है, इसलिए j=1 आज़माएँ: is_pal[2][2]=T, अतः cuts[2] = cuts[1]+1 = 1। उत्तर: 1।
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = [float('inf')] * n
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(i):
if is_pal[j+1][i]:
cuts[i] = min(cuts[i], cuts[j] + 1)
return cuts[n-1]
print(min_cut('aab')) # 1
print(min_cut('ababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab'))समय और स्थान की जटिलता
चरण 1 (पैलिंड्रोम तालिका) में O(n²) समय और O(n²) स्थान लगता है। चरण 2 (कट DP) में n स्थानों पर बाहरी लूप और n विभाजन-बिंदुओं पर आंतरिक लूप चलता है, इसलिए इसमें भी O(n²) समय लगता है। कुल मिलाकर: O(n²) समय, O(n²) स्थान। cuts सारणी के लिए स्थान O(n) तक घटाया जा सकता है, लेकिन पैलिंड्रोम तालिका के लिए अभी भी O(n²) स्थान आवश्यक है। साक्षात्कारकर्ता O(n²) की अपेक्षा करते हैं — Manacher की O(n) विधि सामान्य दायरे से बाहर है।
पैलिंड्रोम तालिका के लिए केन्द्र के चारों ओर विस्तार
पैलिंड्रोम तालिका के लिए अंतराल DP वाली विधि के बजाय, आप केन्द्र के चारों ओर विस्तार करके is_pal भर सकते हैं। प्रत्येक केन्द्र-स्थान के लिए बाहर की ओर विस्तार करें और मिलने वाले सभी पैलिंड्रोम चिह्नित करें। इसमें भी O(n²) समय और O(n²) स्थान लगता है, लेकिन कैश के बेहतर व्यवहार के कारण व्यवहार में यह तेज़ हो सकता है। साक्षात्कार में दोनों विधियाँ मान्य हैं।
def build_pal_expand(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
def expand(l, r):
while l >= 0 and r < n and s[l] == s[r]:
is_pal[l][r] = True
l -= 1; r += 1
for i in range(n):
expand(i, i) # odd-length centres
expand(i, i+1) # even-length centres
return is_pal
print('Expand-around-centre palindrome table built')सभी विभाजनों की गणना (भाग I)
पैलिंड्रोम विभाजन I (एक संबंधित समस्या) में उन सभी मान्य विभाजनों की गणना करनी होती है जिनमें हर उपस्ट्रिंग एक पैलिंड्रोम हो। इसमें पहले से तैयार पैलिंड्रोम तालिका को छँटाई के मार्गदर्शक के रूप में लेकर बैकट्रैकिंग का उपयोग किया जाता है। न्यूनतम-कट DP के विपरीत, जो केवल गिनती करता है, यह घातीय संख्या में समाधानों की गणना करता है और इसके लिए पूरी तरह अलग विधि अपनाई जाती है।
def partition_all(s):
n = len(s)
is_pal = build_pal_expand(s)
result = []
def backtrack(start, path):
if start == n:
result.append(path[:])
return
for end in range(start, n):
if is_pal[start][end]:
path.append(s[start:end+1])
backtrack(end+1, path)
path.pop()
backtrack(0, [])
return result
print(partition_all('aab')) # [['a','a','b'], ['aa','b']]n-1 से cuts का आरंभीकरण
एक सामान्य उपाय है: inf के बजाय cuts[i] = i से आरंभ करें, क्योंकि s[0..i] के लिए सबसे खराब स्थिति में हर वर्ण को अलग-अलग काटना पड़ेगा, जिससे i कट लगेंगे। इससे आपके कोड में inf की जाँच करने की आवश्यकता नहीं रहती। जब is_pal[0][i] सत्य हो, तो मान को 0 से बदल दें। यह आरंभीकरण कट की ऊपरी सीमा स्पष्ट करता है और कोड को थोड़ा सरल बनाता है।
def min_cut_clean(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = list(range(n)) # cuts[i] = i (worst case)
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(1, i+1):
if is_pal[j][i]:
cuts[i] = min(cuts[i], cuts[j-1] + 1)
return cuts[n-1]विकल्प: अलग तालिका के बिना एक-चरणीय DP
एक सुंदर रूपांतर पैलिंड्रोम तालिका और कट DP को एक साथ भरता है। प्रत्येक केन्द्र से पैलिंड्रोम का विस्तार करते समय, cuts सारणी को तुरंत अद्यतन किया जाता है। पैलिंड्रोम s[l..r] के लिए, हम cuts[r] = min(cuts[r], (cuts[l-1]+1 if l > 0 else 0)) से अद्यतन कर सकते हैं। इससे O(n²) वाली अलग तालिका-प्रक्रिया से बचा जा सकता है और समय के दबाव में साक्षात्कार के दौरान इसे लागू करना अधिक साफ़-सुथरा हो सकता है।
विचार करने योग्य सीमांत मामले
पैलिंड्रोम विभाजन II के प्रमुख सीमांत मामले: (1) एक-वर्ण वाली स्ट्रिंग 0 कट लौटाती है; (2) जो स्ट्रिंग पहले से ही पैलिंड्रोम है, वह 0 कट लौटाती है; (3) पूरी तरह अलग-अलग वर्णों वाली स्ट्रिंग के लिए n-1 कट आवश्यक होते हैं; (4) एक जैसे वर्णों वाली स्ट्रिंग (जैसे 'aaaa') के लिए 0 कट आवश्यक होते हैं, क्योंकि पूरी स्ट्रिंग एक पैलिंड्रोम है। हमेशा जाँचें कि आपका समाधान is_pal[0][i] = True वाले शीघ्र-निकास को सही ढंग से संभालता है।
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = list(range(n))
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(1, i+1):
if is_pal[j][i]:
cuts[i] = min(cuts[i], cuts[j-1] + 1)
return cuts[n-1]
print(min_cut('a')) # 0
print(min_cut('aaaa')) # 0
print(min_cut('abc')) # 2साक्षात्कार में संवाद के सुझाव
साक्षात्कार में इस समस्या को प्रस्तुत करते समय दो-चरणीय विधि से शुरुआत करें: पहले पैलिंड्रोम तालिका बनाएँ, फिर cuts सारणी पर 1D DP चलाएँ। कोड लिखने से पहले पुनरावृत्ति को शब्दों में समझाएँ। बताएँ कि पैलिंड्रोम तालिका में O(n²) प्रविष्टियाँ होती हैं और अंतराल DP की पुनरावृत्ति का उपयोग करके प्रत्येक प्रविष्टि O(1) में भरी जाती है। पूर्ण समाधान लिखने से पहले अपने उदाहरण का क्रमवार विवेचन अवश्य करें, ताकि दबाव में भी शुद्धता स्पष्ट हो।
त्वरित जाँच
इस पाठ में दिए गए डेटा संरचनाएँ और एल्गोरिदम — कोडिंग इंटरव्यू तैयारी संबंधी अवधारणाओं की अपनी समझ जाँचें।
पाठ का पुनरावलोकन
इस पाठ में आपने सीखा: पैलिंड्रोम विभाजन II में DP के दो चरण होते हैं — पहले पैलिंड्रोम तालिका की पूर्व-गणना, फिर 1D कट DP चलाना, कट की पुनरावृत्ति उन सभी j के लिए cuts[i] = min(cuts[j-1] + 1) है जहाँ s[j..i] एक पैलिंड्रोम है, और कुल जटिलता O(n²) समय और O(n²) स्थान की है। अगला विषय Burst Balloons समस्या है, जिसमें उल्टे क्रम वाली चतुर अंतराल DP विधि का उपयोग किया जाता है।
एआई शिक्षक के साथ Python सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 30
- पाठ
- 120
अक्सर पूछे जाने वाले प्रश्न
क्या “पैलिंड्रोम विभाजन II” पाठ निःशुल्क है?
हाँ — DSA Interview Prep अध्ययन पथ के 3 तक कोई भी पाठ, जिसमें “पैलिंड्रोम विभाजन II” भी शामिल है, यहाँ वेब पर पूरा पढ़ना निःशुल्क है। इसके बाद CoddyKit PRO हर पाठ अनलॉक करता है, साथ ही अंतर्निर्मित कोड संपादक और चौबीसों घंटे एआई शिक्षक के साथ इंटरैक्टिव अभ्यास भी उपलब्ध कराता है। DSA Interview Prep पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“पैलिंड्रोम विभाजन II” में मैं क्या सीखूँगा?
किसी स्ट्रिंग को पैलिंड्रोमों में विभाजित करने के लिए आवश्यक न्यूनतम कट खोजने हेतु पहले से बनाई गई पैलिंड्रोम तालिका को 1D DP के साथ मिलाइए। आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ DSA Interview Prep का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या DSA Interview Prep शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर DSA Interview Prep शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 3वाँ पाठ है।
“पैलिंड्रोम विभाजन II” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस DSA Interview Prep पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर DSA Interview Prep पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- अंतराल DP पैटर्न और भरने का क्रम
- सबसे लंबा पैलिंड्रोमिक उपअनुक्रम और सबस्ट्रिंग
- पैलिंड्रोम विभाजन II
- गुब्बारे फोड़ना: उलटा अंतराल DP