数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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+ 浏览量
广告