मान लीजिए हमारे पास दो स्ट्रिंग्स s1 और s2 हैं। हमें सबसे लंबी स्ट्रिंग s3 का आकार ढूंढना है जो s1 और s2 दोनों का स्पेशल सबस्ट्रिंग है।
हम कह सकते हैं कि एक स्ट्रिंग x दूसरी स्ट्रिंग y का स्पेशल सबस्ट्रिंग है यदि x को y से 0 या अधिक अक्षर हटाकर उत्पन्न किया जा सकता है।
उदाहरण के लिए, यदि इनपुट है s1 = 'pineapple', s2 = 'people', तो आउटपुट होगा 5 क्योंकि स्पेशल सबस्ट्रिंग 'peple' है, जिसका आकार 5 है।
समाधान दृष्टिकोण
यह क्लासिक लॉन्गेस्ट कॉमन सबसीक्वेंस (LCS) समस्या है जिसे O(n*m) समय में डायनामिक प्रोग्रामिंग का उपयोग करके हल किया जाता है। यहां स्पेस-अनुकूलित संस्करण दो पंक्तियों (prev और cur) का उपयोग करता है।
prevको डिफ़ॉल्ट 0 वाले डिक्शनरी के रूप में आरंभ करें।s1के प्रत्येक अक्षरiके लिए:- नई
curडिक्शनरी बनाएं। s2के प्रत्येक अक्षरjके लिए:- यदि
s1[i] == s2[j], तोcur[j] = prev[j-1] + 1। - अन्यथा
cur[j] = max(cur[j-1], prev[j])।
- यदि
prev = curसेट करें।
- नई
prev[len(s2)-1]लौटाएं।
पायथन कार्यान्वयन
from collections import defaultdict
def solve(s1, s2):
prev = defaultdict(int)
for i in range(len(s1)):
cur = defaultdict(int)
for j in range(len(s2)):
cur[j] = prev[j - 1] + 1 if s1[i] == s2[j] else max(cur[j - 1], prev[j])
prev = cur
return prev[len(s2)-1]
s1 = 'pineapple'
s2 = 'people'
print(solve(s1, s2))
इनपुट
'pineapple', 'people'
आउटपुट
5