forked from haoel/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathminimumWindowSubstring.cpp
More file actions
115 lines (101 loc) · 3.19 KB
/
Copy pathminimumWindowSubstring.cpp
File metadata and controls
115 lines (101 loc) · 3.19 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
// Source : https://oj.leetcode.com/problems/minimum-window-substring/
// Author : Hao Chen
// Date : 2014-07-22
/**********************************************************************************
*
* Given a string S and a string T, find the minimum window in S which will
* contain all the characters in T in complexity O(n).
*
* For example,
* S = "ADOBECODEBANC"
* T = "ABC"
*
* Minimum window is "BANC".
*
* Note:
*
* > If there is no such window in S that covers all characters in T,
* return the emtpy string "".
*
* > If there are multiple such windows, you are guaranteed that there
* will always be only one unique minimum window in S.
*
*
**********************************************************************************/
#include <string.h>
#include <iostream>
#include <string>
using namespace std;
#define INT_MAX 2147483647
string minWindow(string S, string T) {
string win;
if (S.size()<=0 || T.size()<=0 || T.size() > S.size()) return win;
/*
* Declare two "hash map" for ASCII chars
* f[]: represents the char found in string S
* m[]: stores the chars in string T
*/
const int MAX_CHARS = 256;
int f[MAX_CHARS], m[MAX_CHARS];
const int NOT_EXISTED = -1;
const int NOT_FOUND = 0;
memset(m, NOT_EXISTED, sizeof(m));
memset(f, NOT_EXISTED, sizeof(f));
/*
* Go through the T, and inital the m[] and f[]
* Notes: a same char can be appeared multiple times.
*/
for(int i=0; i<T.size(); i++) {
m[T[i]]==NOT_EXISTED ? m[T[i]]=1 : m[T[i]]++ ;
f[T[i]] = NOT_FOUND;
}
int start =-1;
int winSize = INT_MAX;
int letterFound = 0;
int begin = 0;
for(int i=0; i<S.size(); i++) {
/* if S[i] is existed in T*/
if ( m[S[i]] != NOT_EXISTED ){
char ch = S[i];
f[ch]++;
/* if one char has been found enough times, then do not do letterFound++ */
if (f[ch] <= m[ch]) {
letterFound++;
}
if ( letterFound >= T.size() ) {
/*
* Find the beginning of the window
* 1) f[S[begin]] == NOT_EXISTED ===> the char at the `begin` is not in T
* 2) f[S[begin]] > m[S[begin]] ===> a same char appeared more than excepted.
*/
while ( f[S[begin]] == NOT_EXISTED || f[S[begin]] > m[S[begin]] ) {
if ( f[S[begin]] > m[S[begin]] ) {
f[S[begin]]--;
}
begin++;
}
/* Calculate the minimized window size */
if(winSize > i - begin + 1){
start = begin;
winSize = i - begin + 1;
}
}
}
}
if (start>=0 && winSize>0) {
win = S.substr(start, winSize);
}
return win;
}
int main(int argc, char**argv)
{
string S = "ADOBECODEBANC";
string T = "ABC";
if (argc>2){
S = argv[1];
T = argv[2];
}
cout << "S = \"" << S << "\" T=\"" << T << "\"" <<endl;
cout << minWindow(S, T) << endl;
return 0;
}