算法找到子具有其他字符串的所有字符的最小长度 [英] Algorithm to find the minimum length of substring having all characters of other string

问题描述

我有两个字符串：
字符串1 - 你好，你，
字符串2 - OLO （包括空格字符）

I have a two strings:
string1 - hello how are you,
String2 - olo (including space character)

输出：罗浩（HEL 罗浩 w为你）

Output: lo ho ( hello how are you )

罗浩是包含字符串2中的所有字符的唯一字符串。 任何人都可以请提出一个很好的算法，这（我能想到的唯一的OG蛮力算法中 - 为O（n ^ 2）

lo ho is the only substring that contain all characters of string2. Can anyone please suggest a good algorithm for this ( i can think og only Brute Force algo - O(n^2).

另外输出应该是最小长度的字符串（如遇多个选项）。

Also output should be the minimum length string(in case of multiple options).

推荐答案

请2指针→和研究，和一个哈希表 M =字符 - ＆GT;计数为包含字符串的字符不会出现在 S [l..r] 。

Keep two pointer l and r, and a hash table M = character -> count for characters in string2 that do not occur in s[l..r].

最初设定 L = 0 和研究让字符串1 [l..r ] 包含字符串2 的所有字符（如果可能的话）。你可以通过给M删除字符，直到它是空的。

Initially set l = 0 and r so that string1[l..r] contains all the characters of string2 (if possible). You do that by removing characters from M until it is empty.

然后继续通过增加研究一个在每一个步骤，然后递增<​​code>→尽可能同时仍保持中号空。最低在所有的R - L + 1 （子串的长度 S [l..r] ）是溶液

Then proceed by incrementing r by one in each step and then incrementing l as much as possible while still keeping M empty. The minimum over all r - l + 1 (the length of the substring s[l..r]) is the solution.

Pythonish伪code：

Pythonish pseudocode:

n = len(string1)
M = {}   # let's say M is empty if it contains no positive values
for c in string2:
    M[c]++
l = 0
r = -1
while r + 1 < n and M not empty:
    r++
    M[string1[r]]--
if M not empty: 
    return "no solution"
answer_l, answer_r = l, r
while True:
    while M[string1[l]] < 0:
        M[string1[l]]++
        l++
    if r - l + 1 < answer_r - anwer_l + 1:
        answer_l, answer_r = l, r
    r++
    if r == n:
        break
    M[string1[r]]--
return s[answer_l..answer_r]

在为空的检查可以在O实施（1）如果在执行递增和递减操作时，保持积极的条目数

The "is empty" checks can be implemented in O(1) if you maintain the number of positive entries when performing the increment and decrement operations.

让 N 是字符串1 和 M 是长度字符串2 。

注意→和研究被永远只能增加，因此最多有O（n）的增加和因此，在大多数O（n）的指令，在过去外环执行。

Note that l and r are only ever incremented, so there are at most O(n) increments and thus at most O(n) instructions are executed in the last outer loop.

如果 M 被实现为一个数组（我假设字母表是恒定的大小），你得到的运行时 为O（N + M），这是最佳的。如果字母是太大，你可以使用一个哈希表来获得预期的O（N + M）。

If M is implemented as an array (I assume the alphabet is constant size), you get runtime O(n + m), which is optimal. If the alphabet is too large, you can use a hash table to get expected O(n + m).

例如执行：

string1 = "abbabcdbcb"
string2 = "cbb"

# after first loop
M = { 'a': 0, 'b': 2, 'c': 1, 'd': 0 }

# after second loop
l = 0
r = 5
M = { 'a': -2, 'b': -1, 'c': 0, 'd': 0 }

# increment l as much as possible:
l = 2
r = 5
M = { 'a': -1, 'b': 0, 'c': 0, 'd': 0 }

# increment r by one and then l as much as possible
l = 2
r = 6
M = { 'a': -1, 'b': 0, 'c': 0, 'd': -1 }

# increment r by one and then l as much as possible
l = 4
r = 7
M = { 'a': 0, 'b': 0, 'c': 0, 'd': -1 }

# increment r by one and then l as much as possible
l = 4
r = 8
M = { 'a': 0, 'b': 0, 'c': -1, 'd': -1 }

# increment r by one and then l as much as possible
l = 7
r = 9
M = { 'a': 0, 'b': 0, 'c': 0, 'd': 0 }

最好的解决办法是S [7..9]。

The best solution is s[7..9].

这篇关于算法找到子具有其他字符串的所有字符的最小长度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！