找出包含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