hello how are you,
String2 - olo (包括空格字符)lo ho ( hello how are you )
lo ho是唯一包含所有string2字符的子字符串。
请问是否可以提供一个好的算法来解决这个问题（我只能想到Brute Force算法-O（n^2））。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]
n是string1的长度，m是string2的长度。l和r仅进行增加，因此最多会进行O(n)次增加，因此在最后的外部循环中最多执行O(n)个指令。M实现为数组（假设字母表的大小是常量），则运行时为O(n + m)，这是最佳的。如果字母表太大，则可以使用哈希表来获得期望的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[l..r] = bc。诀窍在于与增加“r”相关联的“l”是单调递增的。 - Niklas B.M的工作原理，你可以添加注释，如# M = {o:2, l:1}和# M = {h:-2, e: -1, l: -1, o: 0}以进行说明。 - Aprillion有一个算法，可以在 O(N) 时间内完成。
思路：准备两个数组，即 isRequired[256] 和 isFound[256]，分别用于记录字符串 S 中每个字符的频率以及在解析字符串 S 时已经发现的每个字符的频率。同时，还需要一个计数器来指示何时找到一个有效的窗口。一旦找到了一个有效的窗口，我们就可以移动窗口（向右移动），并保持问题所给出的不变式。
C++ 程序：
void findMinWindow(const char *text, const char *pattern, int &start, int &end){
//Calcuate lengths of text and pattern
int textLen = strlen(text);
int patternLen = strlen(pattern);
// Declare 2 arrays which keep tab of required & found frequency of each char in pattern
int isRequired[256] ; //Assuming the character set is in ASCII
int isFound[256];
int count = 0; //For ascertaining whether a valid window is found
// Keep a tab of minimum window
int minimumWindow = INT_MAX;
//Prepare the isRequired[] array by parsing the pattern
for(int i=0;i<patternLen;i++){
isRequired[pattern[i]]++;
}
//Let's start parsing the text now
// Have 2 pointers: i and j - both starting at 0
int i=0;
int j=0;
//Keep moving j forward, keep i fixed till we get a valid window
for(c=j;c<textLen;c++){
//Check if the character read appears in pattern or not
if(isRequired[text[c]] == 0){
//This character does not appear in the pattern; skip this
continue;
}
//We have this character in the pattern, lets increment isFound for this char
isFound[text[c]]++;
//increment the count if this character satisfies the invariant
if(isFound[text[c]] <= isRequired[text[c]]){
count++;
}
//Did we find a valid window yet?
if(count == patternLen){
//A valid window is found..lets see if we can do better from here on
//better means: increasing i to reduce window length while maintaining invariant
while(isRequired[s[i]] == 0 || isFound[s[i]] > isRequired[s[i]]){
//Either of the above 2 conditions means we should increment i; however we
// must decrease isFound for this char as well.
//Hence do a check again
if(isFound[s[i]] > isRequired[s[i]]){
isFound[s[i]]--;
}
i++;
}
// Note that after the while loop, the invariant is still maintained
// Lets check if we did better
int winLength = j-i+1;
if(winLength < minimumWindow){
//update the references we got
begin = i;
end = j;
//Update new minimum window lenght
minimumWindow = winLength;
}
} //End of if(count == patternLen)
} //End of for loop
}
这是一个使用JavaScript实现的示例。逻辑与@Aprillion上面写的类似。
演示：http://jsfiddle.net/ZB6vm/4/
var s1 = "hello how are you";
var s2 = "olo";
var left, right;
var min_distance;
var answer = "";
// make permutation recursively
function permutate(ar, arrs, k) {
// check if the end of recursive call
if (k == arrs.length) {
var r = Math.max.apply(Math, ar);
var l = Math.min.apply(Math, ar);
var dist = r - l + 1;
if (dist <= min_distance) {
min_distance = dist;
left = l;
right = r;
}
return;
}
for (var i in arrs[k]) {
var v = arrs[k][i];
if ($.inArray(v, ar) < 0) {
var ar2 = ar.slice();
ar2.push(v);
// recursive call
permutate(ar2, arrs, k + 1);
}
}
}
function solve() {
var ar = []; // 1-demension array to store character position
var arrs = []; // 2-demension array to store character position
for (var i = 0; i < s2.length; i++) {
arrs[i] = [];
var c = s2.charAt(i);
for (var k = 0; k < s1.length; k++) { // loop by s1
if (s1.charAt(k) == c) {
if ($.inArray(k, arrs[i]) < 0) {
arrs[i].push(k); // save position found
}
}
}
}
// call permutate
permutate(ar, arrs, 0);
answer = s1.substring(left, right + 1);
alert(answer);
}
solve();
string1中的字符位置，然后选择最小距离的排列方式，使得最低和最高字符位置之间的距离最小。# positions are:
# 01234567890123456
string1 = 'hello how are you'
string2 = 'olo'
# get string1 positions for each character from set(string2)
positions = {'o': [4, 7, 15],
'l': [2, 3]}
# get all permutations of positions (don't repeat the same element)
# then pick the permutation with minimum distance between min and max position
# (obviously, this part can be optimized, this is just an illustration)
permutations = positions['o'] * positions['l'] * positions['o']
permutations = [[4,2,7], [4,3,7], [4,2,15], ...]
the_permutation = [4,3,7]
# voilà
output = string1_without_spaces[3:7]
O(n^2)，而是O(n^3)- 检查每个子字符串本身就是O(n)，而这些子字符串有O(n^2)个。除非你有其他想法？ - amith。 - Niklas B.string1中最小的子字符串，其字符的多重集合是string2字符的多重集合的超集。从问题中的语句“lo ho是唯一包含string2所有字符的子字符串”必须是一个错误，否则对我也毫无意义。 - Niklas B.