算法
学习 yxc的算法
C++代码
class Solution {
public:
static string minWindow(const string &str, const string &tar) {
int tCnt = 0, cntArr[256] = {0};
for (const unsigned char ch : tar) {
if (++cntArr[ch] == 1) {
++tCnt;
}
}
int begin = -1, back = -1;
const int n = static_cast<int>(str.size());
for (int slow = 0, fast = 0, sCnt = 0; fast < n; ++fast) {
const unsigned char chFast = str[fast];
--cntArr[chFast];
if (!cntArr[chFast]) {
++sCnt;
}
for (; slow <= fast && cntArr[str[slow] & 0xff] < 0; ++slow) {
++cntArr[str[slow] & 0xff];
}
if ((sCnt == tCnt) && (begin < 0 || back - begin > fast - slow)) {
begin = slow;
back = fast;
}
}
return begin < 0 ? "" : str.substr(begin, back - begin + 1);
}
};
Java代码
class Solution {
public static String minWindow(final String str, final String tar) {
int tCnt = 0;
final int[] cntArr = new int[256];
for (int i = 0; i < tar.length(); ++i) {
final int ch = tar.charAt(i) & 0xff;
if (++cntArr[ch] == 1) {
++tCnt;
}
}
int begin = -1;
int back = -1;
for (int slow = 0, fast = 0, sCnt = 0; fast < str.length(); ++fast) {
final int chFast = str.charAt(fast) & 0xff;
if (--cntArr[chFast] == 0) {
++sCnt;
}
for (; slow <= fast && cntArr[str.charAt(slow) & 0xff] < 0; ++slow) {
++cntArr[str.charAt(slow) & 0xff];
}
if ((sCnt == tCnt) && (begin < 0 || back - begin > fast - slow)) {
begin = slow;
back = fast;
}
}
return begin < 0 ? "" : str.substring(begin, back + 1);
}
}
Python3代码
class Solution:
def minWindow(self, s: str, t: str) -> str:
tCnt = 0
cntArr = [0] * 256
for ch in t:
ch = ord(ch) & 0xff
cntArr[ch] += 1
if cntArr[ch] == 1:
tCnt += 1
begin = -1
back = -1
slow = 0
sCnt = 0
for fast in range(len(s)):
chFast = ord(s[fast]) & 0xff
cntArr[chFast] -= 1
if cntArr[chFast] == 0:
sCnt += 1
while slow <= fast and cntArr[ord(s[slow]) & 0xff] < 0:
cntArr[ord(s[slow]) & 0xff] += 1
slow += 1
if (sCnt == tCnt) and (begin < 0 or back - begin > fast - slow):
begin = slow
back = fast
if begin < 0:
return ""
return s[begin:back + 1]
Go代码
func minWindow(s string, t string) string {
tCnt := 0
cntArr := [256]int{}
for i := 0; i < len(t); i++ {
ch := t[i] & 0xff
cntArr[ch]++
if cntArr[ch] == 1 {
tCnt++
}
}
begin := -1
back := -1
slow := 0
sCnt := 0
for fast := 0; fast < len(s); fast++ {
chFast := s[fast] & 0xff
cntArr[chFast]--
if cntArr[chFast] == 0 {
sCnt++
}
for ; slow <= fast && cntArr[s[slow]&0xff] < 0; slow++ {
cntArr[s[slow]&0xff]++
}
if (sCnt == tCnt) && (begin < 0 || back-begin > fast-slow) {
begin = slow
back = fast
}
}
if begin < 0 {
return ""
}
return s[begin : back+1]
}