在含有字符串2和3字符串的所有字符无字符串1最小化窗口 [英] Minimum window in String 1 containing all characters from String 2 and no character from String 3
问题描述
好了，这是一个面试问题。而且没有它不是这个问题的副本。
由于3串 - STR1 ， STR2 ， STR3 ：
STR1 =spqrstrupvqw
STR2赛车=SPRT
STR3 =Q
我们已经找到的最小窗口 STR1 ，其中包含 STR2 所有字符的任意顺序，但没有从 STR3字符。在这种情况下，答案是：strup
我来到了这个code：
静态字符串minimumWindow（字符串STR1，字符串STR2，字符串STR3）{
Window类实现可比＆LT;窗口＆GT; {
INT开始;
打算;
公共窗口（INT开始，诠释完）{
this.start =启动;
this.end =结束;
}
公众诠释getEnd（）{
返回结束;
}
公众诠释getStart（）{
返回启动;
}
公众诠释的compareTo（窗口O）{
INT thisDiff =结束 - 启动;
INT thatDiff = o.end - o.start;
返回Integer.compare（thisDiff，thatDiff）;
}
@覆盖
公共字符串的toString（）{
返回[+启动+：+端+];
}
}
//创建字符集为包含（）检查
设置＆LT;性格＆GT; str2Chars =新的HashSet＆LT;＆GT;（）;
对于（CHAR CH：str2.toCharArray（））{
str2Chars.add（CH）;
}
设置＆LT;性格＆GT; str3Chars =新的HashSet＆LT;＆GT;（）;
对于（CHAR CH：str3.toCharArray（））{
str3Chars.add（CH）;
}
//这将存储不包含字符的所有有效窗口
//从STR3。
设置＆LT;窗口＆GT;设置=新TreeSet的＆LT;＆GT;（）;
INT开始= -1;
//这个循环获取每一对指标，使得从子
// [开始，结束），每个窗口不包含STR3任何字符
的for（int i = 0; I＆LT; str1.length（）;我++）{
如果（str3Chars.contains（str1.charAt（ⅰ）））{
set.add（新窗口（开始，我））;
开始= I + 1;
}
}
INT的minLength = Integer.MAX_VALUE的;
字符串minString =;
//遍历窗口查找包含所有的最小长度的字符串
从STR2 //字符
对于（窗窗：集）{
如果（（window.getEnd（） - 1 - window.getStart（））≤; str2.length（））{
继续;
}
对于（INT I = window.getStart（）; I＆LT; window.getEnd（）;我++）{
如果（str2Chars.contains（str1.charAt（ⅰ）））{
//在这个窗口就是与str2中得到第一个字符
//开始从最终迭代来获得最后一个字符
// [开始，结束）子将是最小长度
//串在此窗口
对于（INT J = window.getEnd（） - 1; J＆GT;我; j--）{
如果（str2Chars.contains（str1.charAt（J）））{
字符串s = str1.substring（I，J + 1）;
设置＆LT;性格＆GT; sChars =新的HashSet＆LT;＆GT;（）;
对于（CHAR CH：s.toCharArray（））{
sChars.add（CH）;
}
//如果子包含了所有的字符STR2，
//那么只有它是有效的窗口。
如果（sChars.containsAll（str2Chars））{
INT的len = sChars.size（）;
如果（LEN＆LT;的minLength）{
的minLength = LEN;
minString =秒;
}
}
}
}
}
}
}
//有些时候，一些尾随和前导字符是个案
//在中间重复的地方。我们不需要它们包括在
//的minLength。
//在给定的例子，实际的字符串会来的 - rstrup，但我们
//删除第一个R安全。
StringBuilder的strBuilder =新的StringBuilder（minString）;
而（strBuilder.length（）→1＆安培;＆安培; strBuilder.substring（1）。载（+ strBuilder.charAt（0）））{
strBuilder.deleteCharAt（0）;
}
而（strBuilder.length（）→1＆安培;＆安培; strBuilder.substring（0，strBuilder.length（） - 1）。载（+ strBuilder.charAt（strBuilder.length（） - 1）））{
strBuilder.deleteCharAt（strBuilder.length（） - 1）;
}
返回strBuilder.toString（）;
}
不过，这并不对所有的测试用例工作。它的工作在这个问题中给出的例子。但是，当我提出的code，它没有为2的测试用例。不，我不知道的测试用例，它失败了。
即使在尝试不同的采样输入，我无法找到它失败测试用例。有人可以来看看，什么是错的code？我真的AP preciate，如果有人可以提供一个更好的算法（只是在伪code）。我知道这是真的不是最优化的解决方案，但。
STR1 =spqrstrupvqw
STR2赛车=SPRT
STR3 =Q
我们正在寻找最小的子串，从 STR1 包含所有 STR2 字符的（假设订购）并没有从 STR3字符 ..
I = 1 .. str1.length
光标= 1 .. str2.length
该解决方案必须在窗体上的：
str2.first X X .. X X str2.last
因此，为了检查该子字符串，我们使用游标了 STR2 ，但我们也有避免的约束STR3 字符，因此我们有：
如果str3.contain（STR1 [I]）
光标= 1
其他
如果str1 [我] == STR2 [光标]
光标++
目标检查是：
如果光标＆GT; str2.length
回报的解决方案
其他
如果我＆GT; = str1.length
返回未找到
和优化，您可以跳到下一个先行是：
前瞻= {STR2 [光标]或{X |的X STR3}}
如果 STR2 是没有下令
I = 1 .. str1.length
查找= {X |的X STR2}
该解决方案必须在窗体上的：
STR2 [X] X X .. X X STR2 [X]
因此，为了检查该子字符串，我们使用核对表 STR2 ，但我们也有避免的约束STR3 字符，因此我们有：
如果str3.contain（STR1 [I]）
查找= {X |的X STR2}
其他
如果lookup.contain（STR1 [I]）
lookup.remove（STR1 [I]）
目标检查是：
如果查找是空的
回报的解决方案
其他
如果我＆GT; = str1.length
返回未找到
和优化，您可以跳到下一个先行是：
前瞻= {{X |的X查找}或{X |的X STR3}}
code
类解决方案
{
私有静态的ArrayList＆LT;性格＆GT; getCharList（字符串str）
{
返回Arrays.asList（str.getCharArray（））;
}
私有静态无效的FindFirst（一个字符串，字符串B，串c）
{
INT光标= 0;
INT开始= -1;
INT端= -1;
ArrayList的＆LT;性格＆GT;流= getCharList（一）;
ArrayList的＆LT;性格＆GT;查找= getCharList（B）;
ArrayList的＆LT;性格＆GT;避免= getCharList（C）;
对于（字符ch：流）
{
如果（avoid.contains（CH））
{
查找= getCharList（B）;
开始= -1;
结束= -1;
}
其他
{
如果（lookup.contains（CH））
{
lookup.remove（CH）
如果（开始== -1）启动=光标;
结束=光标;
}
}
如果（lookup.isEmpty（））
打破;
光标++;
}
如果（lookup.isEmpty（））
{
的System.out.println（发现了在（+启动+：+端+））;
}
其他
{
的System.out.println（找不到）;
}
}
}
Ok, this is an interview question. And no it's not a duplicate of this question.
Given 3 strings - str1, str2, str3:
str1 = "spqrstrupvqw"
str2 = "sprt"
str3 = "q"
We've to find the minimum window in str1, which contains all characters from str2 in any order, but no character from str3. In this case the answer would be: "strup".
I've come up with this code:
static String minimumWindow(String str1, String str2, String str3) {
class Window implements Comparable<Window> {
int start;
int end;
public Window(int start, int end) {
this.start = start;
this.end = end;
}
public int getEnd() {
return end;
}
public int getStart() {
return start;
}
public int compareTo(Window o) {
int thisDiff = end - start;
int thatDiff = o.end - o.start;
return Integer.compare(thisDiff, thatDiff);
}
@Override
public String toString() {
return "[" + start + " : " + end + "]";
}
}
// Create Sets of characters for "contains()" check
Set<Character> str2Chars = new HashSet<>();
for (char ch: str2.toCharArray()) {
str2Chars.add(ch);
}
Set<Character> str3Chars = new HashSet<>();
for (char ch: str3.toCharArray()) {
str3Chars.add(ch);
}
// This will store all valid window which doesn't contain characters
// from str3.
Set<Window> set = new TreeSet<>();
int begin = -1;
// This loops gets each pair of index, such that substring from
// [start, end) in each window doesn't contain any characters from str3
for (int i = 0; i < str1.length(); i++) {
if (str3Chars.contains(str1.charAt(i))) {
set.add(new Window(begin, i));
begin = i + 1;
}
}
int minLength = Integer.MAX_VALUE;
String minString = "";
// Iterate over the windows to find minimum length string containing all
// characters from str2
for (Window window: set) {
if ((window.getEnd() - 1 - window.getStart()) < str2.length()) {
continue;
}
for (int i = window.getStart(); i < window.getEnd(); i++) {
if (str2Chars.contains(str1.charAt(i))) {
// Got first character in this window that is in str2
// Start iterating from end to get last character
// [start, end) substring will be the minimum length
// string in this window
for (int j = window.getEnd() - 1; j > i; j--) {
if (str2Chars.contains(str1.charAt(j))) {
String s = str1.substring(i, j + 1);
Set<Character> sChars = new HashSet<>();
for (char ch: s.toCharArray()) {
sChars.add(ch);
}
// If this substring contains all characters from str2,
// then only it is valid window.
if (sChars.containsAll(str2Chars)) {
int len = sChars.size();
if (len < minLength) {
minLength = len;
minString = s;
}
}
}
}
}
}
}
// There are cases when some trailing and leading characters are
// repeated somewhere in the middle. We don't need to include them in the
// minLength.
// In the given example, the actual string would come as - "rstrup", but we
// remove the first "r" safely.
StringBuilder strBuilder = new StringBuilder(minString);
while (strBuilder.length() > 1 && strBuilder.substring(1).contains("" + strBuilder.charAt(0))) {
strBuilder.deleteCharAt(0);
}
while (strBuilder.length() > 1 && strBuilder.substring(0, strBuilder.length() - 1).contains("" + strBuilder.charAt(strBuilder.length() - 1))) {
strBuilder.deleteCharAt(strBuilder.length() - 1);
}
return strBuilder.toString();
}
But it doesn't work for all the test cases. It does work for the example given in this question. But when I submitted the code, it failed for 2 test cases. No I don't know the test cases for which it failed.
Even after trying various sample inputs, I couldn't find a test case for which it fails. Can someone take a look as to what is wrong with the code? I would really appreciate if someone can give a better algorithm (Just in pseudo-code). I know this is really not the optimized solution though.
str1 = "spqrstrupvqw"
str2 = "sprt"
str3 = "q"
We're looking for the minimum sub-string from str1 that contain all str2 characters (assume ordered) and no characters from str3 ..
i = 1 .. str1.length
cursor = 1 .. str2.length
The solution must be on the form:
str2.first X X .. X X str2.last
So to check for that sub-string we use a cursor over str2, but we also have the constraint of avoiding str3 characters, so we have:
if str3.contain(str1[i])
cursor = 1
else
if str1[i] == str2[cursor]
cursor++
Goal check is:
if cursor > str2.length
return solution
else
if i >= str1.length
return not-found
And for optimization, you can skip to the next look-ahead which is:
look-ahead = { str2[cursor] or { X | X in str3 }}
In case str2 is not ordered:
i = 1 .. str1.length
lookup = { X | X in str2 }
The solution must be on the form:
str2[x] X X .. X X str2[x]
So to check for that sub-string we use a check-list str2, but we also have the constraint of avoiding str3 characters, so we have:
if str3.contain(str1[i])
lookup = { X | X in str2 }
else
if lookup.contain(str1[i])
lookup.remove(str1[i])
Goal check is:
if lookup is empty
return solution
else
if i >= str1.length
return not-found
And for optimization, you can skip to the next look-ahead which is:
look-ahead = {{ X | X in lookup } or { X | X in str3 }}
Code
class Solution
{
private static ArrayList<Character> getCharList (String str)
{
return Arrays.asList(str.getCharArray());
}
private static void findFirst (String a, String b, String c)
{
int cursor = 0;
int start = -1;
int end = -1;
ArrayList<Character> stream = getCharList(a);
ArrayList<Character> lookup = getCharList(b);
ArrayList<Character> avoid = getCharList(c);
for(Character ch : stream)
{
if (avoid.contains(ch))
{
lookup = getCharList(b);
start = -1;
end = -1;
}
else
{
if (lookup.contains(ch))
{
lookup.remove(ch)
if (start == -1) start = cursor;
end = cursor;
}
}
if (lookup.isEmpty())
break;
cursor++;
}
if (lookup.isEmpty())
{
System.out.println(" found at ("+start+":"+end+") ");
}
else
{
System.out.println(" not found ");
}
}
}
这篇关于在含有字符串2和3字符串的所有字符无字符串1最小化窗口的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
