找出包含Python中特定字符串的最小子字符串的程序
假设我们有两个字符串s和t。我们必须找到s中最小的子字符串，其中t也是子字符串的子序列。如果该类型的子字符串不存在，我们将返回一个空白字符串，如果有多个最小的子字符串，我们将选择最左边的一个。
因此，如果输入类似于s=“abcbfbghfb”，t=“fg”，则输出将为fbg
为了解决这个问题，我们将遵循以下步骤-
N：=S的大小
dp：=用无穷大初始化的大小为N的新列表
对于介于0到N−1的i
dp[i]：=1
如果S[i]与T[0]相同，则
对于范围1至T−1的j
如果S[i]与T[j]相同，则
dp：=dp2
dp2[i]：=dp[prev_i]+（i−prev_i）
prev_i：=从最后返回T[j−1]的值
如果prev_i不为null，则
last[S[i]]：=i
最后：=一张新映射
dp2：=一个新的大小为N的列表，并用无穷大初始化
对于0到N范围内的i，执行
m：=dp的最小值
i：=返回dp中包含m的索引
如果m是无穷大，则
返回空白字符串
返回S[从索引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