मान लीजिए कि हमारे पास दो तार s और t हैं। हमें s में सबसे छोटा सबस्ट्रिंग ढूंढ़ना है, जहां t भी सबस्ट्रिंग का एक परवर्ती क्रम है। यदि उस प्रकार का सबस्ट्रिंग मौजूद नहीं है, तो हम एक रिक्त स्ट्रिंग लौटाएंगे, और यदि कई छोटे सबस्ट्रिंग हैं, तो हम सबसे बाईं ओर ले जाएंगे।
इसलिए, यदि इनपुट s ="abcbfbghfb", t ="fg" जैसा है, तो आउटपुट fbg होगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एन:=एस का आकार
-
डीपी:=आकार एन की एक नई सूची अनंत के साथ आरंभ की गई
-
0 से N − 1 की सीमा में i के लिए, करें
-
यदि S[i], T[0] के समान है, तो
-
डीपी [i] :=1
-
-
-
j के लिए श्रेणी 1 से T-1 के आकार तक, करें
-
अंतिम:=एक नया नक्शा
-
dp2 :=आकार N की एक नई सूची अनंत के साथ आरंभ की गई
-
मेरे लिए 0 से N की सीमा में, करें
-
यदि S[i], T[j] के समान है, तो
-
prev_i :=अंतिम से T[j - 1] का मान लौटाएं
-
अगर prev_i रिक्त नहीं है, तो
-
dp2[i] :=dp[prev_i] + (i - prev_i)
-
-
अंतिम [एस [i]]:=मैं
-
-
डीपी:=डीपी2
-
-
-
मी :=न्यूनतम डीपी
-
i :=dp में m युक्त इंडेक्स लौटाएं
-
अगर m अनंत है, तो
-
रिक्त स्ट्रिंग लौटाएं
-
-
रिटर्न एस [इंडेक्स से i - dp[i] + 1 से i]
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
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")) इनपुट
"abcbfbghfb","fg"
आउटपुट
fbg
