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

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

因此，如果输入类似于 s = "abcbfbghfb"，t = "fg"，则输出将是 fbg

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

  • N := S 的大小

  • 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]

让我们查看以下实现以更好地理解：

示例

 实时演示

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

更新于: 2020-12-26

1K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告