在包含Python中另一个字符串的所有字符的字符串中找到最小的窗口

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

假设我们有两个字符串s1和s2，我们必须在s1中找到最小的子字符串，这样才能有效地使用s2的所有字符。

因此，如果输入像s1 =“我是学生”，s2 =“ mdn”，则输出将是“ ma studen”

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

  • N：= 26

  • str_len：= main_str的大小，patt_len：=模式的大小

  • 如果str_len <patt_len，则

    • 不返回

  • hash_pat：=大小为N的数组，并用0填充

  • hash_str：=大小为N的数组，并用0填充

  • 对于范围在0到patt_len之间的我，执行

    • hash_pat [（（pattern [i]）的ASCII码]：= 1

  • 开始：= 0，start_index：= -1，min_len：= inf

  • 计数：= 0

  • 对于范围0到str_len的j，执行

    • 而hash_str [（main_str [start]）的ASCII]> hash_pat [（main_str [start]）的ASCII]或hash_pat [（main_str [start]）的ASCII]与0相同，

    • len_window：= j-开始+ 1

    • 如果min_len> len_window，则

    • hash_str [（main_str [start]）的ASCII]：= hash_str [（main_str [start]）的ASCII]-1

    • 如果hash_str [（main_str [start]）的ASCII]> hash_pat [（main_str [start]）的ASCII]，则

    • 开始：=开始+ 1

    • min_len：= len_window

    • start_index：=开始

    • 数：=数+ 1

    • hash_str [（（main_str [j]）的ASCII]：= hash_str [（（main_str [j]）的ASCII）] + 1

    • 如果hash_pat [（main_str [j]）的ASCII不等于0，并且hash_str [（main_str [j]）的ASCII] <= hash_pat [（main_str [j]）的ASCII]，则

    • 如果计数与patt_len相同，则

    • 如果start_index与-1相同，则

      • 不返回

    • 返回main_str的子字符串[从索引start_index到start_index + min_len]

    示例

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

    N = 256
    def get_pattern(main_str, pattern):
       str_len = len(main_str)
       patt_len = len(pattern)
       if str_len < patt_len:
          return None
       hash_pat = [0] * N
       hash_str = [0] * N
       for i in range(0, patt_len):
          hash_pat[ord(pattern[i])] += 1
       start, start_index, min_len = 0, -1, float('inf')
       count = 0
       for j in range(0, str_len):
          hash_str[ord(main_str[j])] += 1
          if (hash_pat[ord(main_str[j])] != 0 and hash_str[ord(main_str[j])] <= hash_pat[ord(main_str[j])]):
             count += 1
          if count == patt_len:
             while (hash_str[ord(main_str[start])] > hash_pat[ord(main_str[start])] or hash_pat[ord(main_str[start])] == 0):
          if (hash_str[ord(main_str[start])] > hash_pat[ord(main_str[start])]):
             hash_str[ord(main_str[start])] -= 1
             start += 1
          len_window = j - start + 1
          if min_len > len_window:
             min_len = len_window
             start_index = start
       if start_index == -1:
          return None
       return main_str[start_index : start_index + min_len]
    main_str = "I am a student"
    pattern = "mdn"
    print(get_pattern(main_str, pattern))

    输入值

    "I am a student", "mdn"

    输出结果

    m a studen

    以上是 在包含Python中另一个字符串的所有字符的字符串中找到最小的窗口 的全部内容， 来源链接： utcz.com/z/343449.html

    回到顶部