# 76. 最小覆盖子串

2020/12/26 19:31

#### 解题代码

   public String minWindow(String s, String t) {

if (s == null || s.length() == 0 || t == null || t.length() == 0) {
return "";
}

/**
* 总共128个字符
*/
int[] needs = new int[128];

int tsize = t.length();

for (int i = 0; i < tsize; i++) {
needs[t.charAt(i)]++;

}

int left = 0, right = 0;

/**
* 有效字符串的起始位置
*/
int start = 0;
/**
* 有效字符串的长度
*/
int size = Integer.MAX_VALUE;

int needSize = t.length();

while (right < s.length()) {

if (needs[s.charAt(right)] > 0) {
needSize--;
}
/**
* 不是需要的字符也纳入窗口中，并且赋值小于0
*/
needs[s.charAt(right)]--;

if (needSize == 0) {

/**
* 找到满足目标字符串中的第一个元素
*/

while (left < right && needs[s.charAt(left)] < 0) {
//释放左边无用的字符
needs[s.charAt(left)]++;
left++;//指针右移
}

int tempSize = right - left + 1;

if (tempSize < size) {
start = left;
size = tempSize;
}

needs[s.charAt(left)]++;

left++;

needSize++;

}
right++;

}
return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
}


#### 解法2


public String minWindow(String s, String t) {

if (s == null || s.length() == 0 || t == null || t.length() == 0) {
return "";
}

int rigtMin = findRight(s, t);

int leftMax = findLeft(s,t);

return s.substring(leftMax,rigtMin);
}

private int findLeft(String s, String t) {

int left = 0;

while (true) {
String temp = s.substring(left, s.length());

if (temp.contains(t)) {
left++;
} else {
left--;
return left;
}
}
}

private int findRight(String s, String t) {

int right = s.length();

while (true) {
String temp = s.substring(0, right);

if (temp.contains(t)) {
right--;
} else {
right++;
return right;
}
}
}

}


0 评论
0 收藏
0