在Python中查找包含特定字符串的最小子串的程序

假设我们有两个字符串s和t。我们必须在s中查找最小的子字符串，其中t也是子序列。如果不存在这种类型的子字符串，则会返回一个空字符串，如果有多个最小子字符串，则将取最左边的一个。

因此，如果输入如下：s =“abcbfbghfb”，t =“fg”，那么输出将是fbg。

要解决这个问题，我们将遵循以下步骤：

N：将S的大小设为N
dp：一个大小为N的新列表，初始化为正无穷数
对于i从0到N-1，循环执行以下操作：
- 如果S[i]与T[0]相同，则
  - dp[i]：= 1
对于j从1到T的大小-1，循环执行以下操作：
- last ：一个新的映射
- dp2：一个大小为N的新列表，初始化值为无限数
- 对于i从0到N，循环执行以下操作：
  - 如果S [i]与T [j]相同，则
  - prev_i：从last返回T [j-1]的值
  - 如果prev_i不为空，则
    - dp2[i]：= dp[prev_i]+（i-prev_i）
  - last [S [i]]：= i
  - dp：= dp2
m：dp中的最小值
i：返回dp中包含m的索引
如果m为正无穷数，则
- 返回空字符串
返回S [从索引i-dp [i]+1到i的内容]

让我们看以下实现理解得更好-

更多Python相关文章，请阅读：Python 教程

示例

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"))