Longest Common Subsequence
DP table से दो strings को align करें
Longest Common Subsequence, CoddyKit पर Competitive Programming Academy का एक निःशुल्क पाठ है। यह 4 में से 3वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह Competitive Programming Academy सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। Competitive Programming Academy पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
उपअनुक्रम क्या होता है
उपअनुक्रम वर्णों का क्रम बनाए रखता है, लेकिन कुछ वर्णों को छोड़ सकता है। 'abcde' से आप 'ace' ले सकते हैं, लेकिन 'aec' कभी नहीं।
LCS का लक्ष्य
दो स्ट्रिंग दिए जाने पर, सबसे लंबा साझा उपअनुक्रम वह सबसे लंबा अनुक्रम है जो दोनों में समान सापेक्ष क्रम में दिखाई देता है।
ग्रिड पर आइए
दोनों स्ट्रिंग के उपस्ट्रिंगों की तुलना कीजिए। उनकी लंबाइयों पर आधारित 2D तालिका इसे परिचित ग्रिड DP समस्या में बदल देती है।
अवस्था निर्धारित कीजिए
मान लीजिए dp[i][j], A के पहले i वर्णों और B के पहले j वर्णों के LCS की लंबाई है।
जब वर्ण समान हों
यदि A[i-1] और B[j-1] समान हैं, तो वह साझा अक्षर LCS को एक से बढ़ाता है। आप विकर्ण मान dp[i-1][j-1] में एक जोड़ते हैं।
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1जब वे अलग हों
यदि अक्षर अलग हों, तो किसी एक स्ट्रिंग से एक वर्ण हटाकर बेहतर परिणाम रखिए। आप दोनों पड़ोसियों में से अधिकतम लेते हैं।
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])आधार स्थिति
एक खाली उपस्ट्रिंग में कुछ भी साझा नहीं होता, इसलिए LCS की लंबाई शून्य होती है। पंक्ति 0 और स्तंभ 0 में सभी मान शून्य रहते हैं।
dp = [[0] * (m+1) for _ in range(n+1)]एक अतिरिक्त पंक्ति और स्तंभ
तालिका का आकार n+1 गुणा m+1 रखने पर शून्यों की एक अतिरिक्त सीमा मिलती है। इससे किनारों पर परेशान करने वाली सीमा-जाँच हट जाती है।
इसे पूरा भरिए
i और j पर 1 से आगे की ओर लूप चलाइए। हर कोशिका को केवल ऊपर, बाएँ और विकर्ण के मान चाहिए, जिनकी गणना पहले ही हो चुकी है।
for i in range(1, n+1):
for j in range(1, m+1):
...लंबाई पढ़िए
पूरे LCS की लंबाई कोने में होती है। हर कोशिका भर जाने के बाद उत्तर dp[n][m] है।
length = dp[n][m]जटिलता
आप हर कोशिका को एक बार देखते हैं, इसलिए कार्य में O(n गुणा m) समय और स्मृति लगती है। यह कुछ हज़ार वर्णों तक की स्ट्रिंग को आसानी से संभाल लेता है।
त्वरित जाँच
वर्तमान वर्ण A[i-1] और B[j-1] समान हैं। कौन-सा अद्यतन सही है?
पुनरावलोकन: LCS
n+1 गुणा m+1 की तालिका बनाइए: समानता पर विकर्ण में एक जोड़िए, अन्यथा पड़ोसी मानों में से अधिकतम लीजिए। कोने में लंबाई होती है। 🔗
एआई शिक्षक के साथ Python सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 30
- पाठ
- 120
अक्सर पूछे जाने वाले प्रश्न
क्या “Longest Common Subsequence” पाठ निःशुल्क है?
हाँ—“Longest Common Subsequence” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और Competitive Programming Academy पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। Competitive Programming Academy पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“Longest Common Subsequence” में मैं क्या सीखूँगा?
DP table से दो strings को align करें आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ Competitive Programming Academy का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या Competitive Programming Academy शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर Competitive Programming Academy शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 3वाँ पाठ है।
“Longest Common Subsequence” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस Competitive Programming Academy पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर Competitive Programming Academy पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- Grid पर Paths गिनना
- Obstacles के साथ Minimum Path Sum
- Longest Common Subsequence
- Edit Distance Step by Step