पायथन में विशिष्ट स्ट्रिंग समाहित करने वाली सबसे छोटी सबस्ट्रिंग ढूंढने का प्रोग्राम

मान लीजिए हमारे पास दो स्ट्रिंग्स s और t हैं। हमें s में सबसे छोटी सबस्ट्रिंग ढूंढनी है जहां t उस सबस्ट्रिंग का सबसीक्वेंस भी हो। यदि उस प्रकार की सबस्ट्रिंग मौजूद नहीं है, तो हम खाली स्ट्रिंग लौटाएंगे, और यदि कई सबसे छोटी सबस्ट्रिंग्स हैं, तो हम बाएं वाली को लेंगे।

उदाहरण के लिए, यदि इनपुट s = "abcbfbghfb", t = "fg" है, तो आउटपुट fbg होगा।

समाधान दृष्टिकोण

हम डायनामिक प्रोग्रामिंग का उपयोग करते हैं जहां dp[i] इंडेक्स i पर समाप्त होने वाले T के प्रीफिक्स से मेल खाने वाली न्यूनतम लंबाई स्टोर करता है।

एल्गोरिदम चरण:

1. N = len(S), dp = आकार N की सूची जिसे infinity से इनिशियलाइज़ किया गया
2. प्रत्येक i (0 से N-1) के लिए:
• यदि S[i] == T[0], तो dp[i] = 1
3. j 1 से len(T)-1 तक के लिए:
• last = खाली मैप, dp2 = infinity से इनिशियलाइज़्ड सूची
• प्रत्येक i (0 से N-1) के लिए:
• यदि S[i] == T[j]:
• prev_i = last.get(T[j-1], None)
• यदि prev_i None नहीं है: dp2[i] = dp[prev_i] + (i - prev_i)
• last[S[i]] = i
• dp = dp2
4. m = min(dp), i = dp.index(m)
5. यदि m == infinity, तो खाली स्ट्रिंग लौटाएं
6. S[i - dp[i] + 1 : i + 1] लौटाएं

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

class Solution:
    def solve(self, S, T):
        INF = float("inf")
        N = len(S)
        dp = [INF] * N
        
        for i in range(N):
            if S[i] == T[0]:
                dp[i] = 1
        
        for j in range(1, len(T)):
            last = {}
            dp2 = [INF] * N
            for i in range(N):
                if S[i] == T[j]:
                    prev_i = last.get(T[j-1], None)
                    if prev_i is not None:
                        dp2[i] = dp[prev_i] + (i - prev_i)
                    last[S[i]] = i
            dp = dp2
        
        m = min(dp)
        i = dp.index(m)
        if m == INF:
            return ""
        return S[i - dp[i] + 1 : i + 1]

ob = Solution()
print(ob.solve("abcbfbghfb", "fg"))  # fbg

इनपुट

"abcbfbghfb", "fg"

आउटपुट

fbg

व्याख्या:

S = "abcbfbghfb", T = "fg"

• 'f' इंडेक्स 6 पर मिला
• 'g' इंडेक्स 7 पर मिला
• सबस्ट्रिंग S[6:8] = "fg" लेकिन "fbg" (इंडेक्स 5-7) भी 'f' और 'g' को सबसीक्वेंस के रूप में समाहित करता है
• न्यूनतम लंबाई 3: "fbg"