程序以查找Python中包含给定子字符串的最小字符串大小

Z时代
2024-01-10
分类：综合

假设我们有两个字符串s和t，我们必须找到s中包含所有t字符的最小子字符串的大小。如果不存在这样的子字符串，则返回-1。

因此，如果输入像s =“ thegrumpywizardmakes” t =“ wake”，则输出将为10，因为包含“ wake”的最短子字符串为“ wizardmake”（长度为10）。

范例(Python)

让我们看下面的实现以更好地理解-

class Solution:
   def solve(self, a, b):
      counter = {}
      for char in b:
         counter[char] = counter.get(char, 0) + 1
      start = 0
      min_subs = float("inf")
      rem = len(counter)
      for end in range(len(a)):
         current = a[end]
         if current in counter:
            counter[current] -= 1
            if counter[current] == 0:
               rem -= 1
         while rem == 0:
            prev_char = a[start]
            if prev_char in counter:
               counter[prev_char] += 1
               if counter[prev_char] > 0:
                  rem += 1
               min_subs = min(min_subs, end - start + 1)
               start += 1
      return min_subs if min_subs != float("inf") else -1
ob = Solution()
s = "thegrumpywizardmakes"
t = "wake"
print(ob.solve(s, t))