在字符串x中查找包含另一个字符串的所有字符的最小窗口宽度y.例如:
String x = "coobdafceeaxab"
String y = "abc"
答案应该是5,因为x其中包含所有三个字母的最短子字符串y是"bdafc".
我可以想到一个复杂的天真解决方案O(n^2 * log(m)),在哪里n = len(x)和m = len(y).有谁能建议更好的解决方案？谢谢.
更新:现在想起来,如果我将我的设置更改为tr1::unordered_map,那么我可以将复杂性降低到O(n^2),因为插入和删除都应该是O(1).
Jac*_*ack 21
时间:O(n)(一次通过)
空间:O(k)
我就是这样做的:
为字符串Y中的所有字符创建一个哈希表.(我假设Y中的所有字符都不同).
第一遍:
从字符串X的第一个字符开始.
更新哈希表,对于exa:对于键'a'输入位置(比如说1).
继续这样做,直到你从Y获得所有字符(直到哈希表中的所有键都有值).
如果再次获得某个角色,请更新其较新的值并删除较旧的角色.
第一次传递后,从哈希表和最大值中获取最小值.
这是迄今为止观察到的最小窗口.
现在,转到字符串X中的下一个字符,更新哈希表,看看是否得到更小的窗口.
让我们举个例子:
String x ="coobdafceeaxab"
String y ="abc"
首先从Y的字符初始化哈希表.h
[a] = -1
h [b] = -1
h [c] = -1
现在,从X的
第一个字符开始.第一个字符是c,h [c] = 0
第二个字符(o)不是哈希的一部分,跳过它.
..
第四个字符(b),h [b] = 3
..
第六个字符(a),输入哈希表h [a] = 5.
现在,哈希表中的所有键都有一些值.
最小值为0(c),最高值为5(a),最小窗口为6(0到5).
第一轮完成.
采取下一个角色.f不是哈希表的一部分,跳过它.
下一个字符(c),更新哈希表h [c] = 7.
找到新窗口,最小值为3(b),最高值为7(c).
新窗口是3到7 => 5.
继续这样做直到字符串X的最后一个字符.
我希望它现在清楚.
关于从哈希中查找最大值和最小值存在一些问题.
我们可以维护已排序的链接列表并将其映射到哈希表.
每当链接列表中的任何元素发生更改时,都应将其重新映射到哈希表.
这两个操作都是O(1)
总空间为m + m
以下是上述问题的小型可视化:对于"coobdafceeaxab"和"abc"
step-0:
initial doublely linked-list = NULL
Initial hash-table = NULL
步骤1:
头< - > [c,0] < - >尾部
h [c] = [0,'指向LL中c节点的指针']
步骤2:
头< - > [c,0] < - > [b,3] < - >尾部
h [c] = [0,'指向LL中c节点的指针'],h [b] = [3 ,'指向LL中b节点的指针',
步骤3:
头< - > [c,0] < - > [b,3] < - > [a,5] < - >尾部
h [c] = [0,'指向LL中c节点的指针'] ,h [b] = [3,'指向LL中b节点的指针'],h [a] = [5,'指向LL中节点的指针']
最小窗口=>与尾部和头部的差异=>(5- 0)+1 =>长度:6
步骤4:
在此处更新C到索引7的条目.(从链表中删除'c'节点并附加在尾部)
Head < - > [b,3] < - > [a,5] < - > [c,7] < - > tail
h [c] = [7,'LL指向c节点的新指针'],h [b] = [3,'指向LL中b节点的指针'],h [a] = [5,'指向LL中节点的指针'],
最小窗口=>与尾部和头部的差异=>(7-3)+1 =>长度:5
等等..
注意,上面的链表更新和哈希表更新都是O(1).
如果我错了请纠正我..
时间复杂度:O(n)一次通过
空间复杂度:O(k)其中k是字符串Y的长度
这是我在 C++ 中的解决方案：
int min_width(const string& x, const set<char>& y) {
vector<int> at;
for (int i = 0; i < x.length(); i++)
if (y.count(x[i]) > 0)
at.push_back(i);
int ret = x.size();
int start = 0;
map<char, int> count;
for (int end = 0; end < at.size(); end++) {
count[x[at[end]]]++;
while (count[x[at[start]]] > 1)
count[x[at[start++]]]--;
if (count.size() == y.size() && ret > at[end] - at[start] + 1)
ret = at[end] - at[start] + 1;
}
return ret;
}
编辑：这是杰克想法的实现。它与我的时间复杂度相同，但没有让您感到困惑的内部循环。
int min_width(const string& x, const set<char>& y) {
int ret = x.size();
map<char, int> index;
set<int> index_set;
for (int j = 0; j < x.size(); j++) {
if (y.count(x[j]) > 0) {
if (index.count(x[j]) > 0)
index_set.erase(index[x[j]]);
index_set.insert(j);
index[x[j]] = j;
if (index.size() == y.size()) {
int i = *index_set.begin();
if (ret > j-i+1)
ret = j-i+1;
}
}
}
return ret;
}
在 Java 中，它可以用 LinkedHashMap 很好地实现：
static int minWidth(String x, HashSet<Character> y) {
int ret = x.length();
Map<Character, Integer> index = new LinkedHashMap<Character, Integer>();
for (int j = 0; j < x.length(); j++) {
char ch = x.charAt(j);
if (y.contains(ch)) {
index.remove(ch);
index.put(ch, j);
if (index.size() == y.size()) {
int i = index.values().iterator().next();
if (ret > j - i + 1)
ret = j - i + 1;
}
}
}
return ret;
}
循环内的所有操作都需要恒定时间（假设散列元素正确分散）。
我发现这很不错O(N)的时间复杂度在这里版本http://leetcode.com/2010/11/finding-minimum-window-in-s-which.html,并缩短了它略有(除去继续在第一,而,这允许简化第二个while循环的条件).请注意,此解决方案允许在第二个字符串中使用重复项,而上述许多答案都不允许.
private static String minWindow(String s, String t) {
int[] needToFind = new int[256];
int[] hasFound = new int[256];
for(int i = 0; i < t.length(); ++i) {
needToFind[t.charAt(i)]++;
}
int count = 0;
int minWindowSize = Integer.MAX_VALUE;
int start = 0, end = -1;
String window = "";
while (++end < s.length()) {
char c = s.charAt(end);
if(++hasFound[c] <= needToFind[c]) {
count++;
}
if(count < t.length()) continue;
while (hasFound[s.charAt(start)] > needToFind[s.charAt(start)]) {
hasFound[s.charAt(start++)]--;
}
if(end - start + 1 < minWindowSize) {
minWindowSize = end - start + 1;
window = s.substring(start, end + 1);
}
}
return window;
}