leetcode/src/Minimum_Window_Substring.cpp at master · zyx4843/leetcode · GitHub

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
115
116
117
118
119
// Source : https://oj.leetcode.com/problems/minimum-window-substring/
// Author : zheng yi xiong
// Date   : 2015-01-15

/**********************************************************************************
*
* 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 "stdafx.h"
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
	string minWindow(string S, string T) {
		if (T.empty() || S.empty() || T.size() > S.size())
		{
			return "";
		}

		vector<int>  vec_bInT_num(256, 0);
		vector<int>	 vec_appere_num(256, 0);
		int size_T = T.size(), size_S = S.size();
		for (int i = 0; i < size_T; ++i)
		{
			++vec_bInT_num[T[i]];
		}

		int curNum = 0, minNum = size_S + 1;
		int start = 0, min_start = 0;
		for (int i = 0; i < size_S; ++i)
		{
			if (0 != vec_bInT_num[S[i]])
			{
				++vec_appere_num[S[i]];
				if (0 == curNum)
				{
					start = i;
					if (1 == size_T)
					{
						return T;
					}
					else
					{
						++curNum;
						continue;
					}
				}

				if (vec_bInT_num[S[i]] >= vec_appere_num[S[i]])
				{
					++curNum;
					if (size_T == curNum)
					{
						if ( minNum > (i - start) )
						{
							minNum = i - start;
							min_start = start;
						}
					}
				}
				else
				{
					for (int j = start; j <= i; ++j)
					{
						if (0 != vec_bInT_num[S[j]])
						{
							if (vec_bInT_num[S[j]] >= vec_appere_num[S[j]])
							{
								start = j;
								if (size_T == curNum)
								{
									if ( minNum > (i - start) )
									{
										minNum = i - start;
										min_start = start;
									}
								}
								break;
							}
							--vec_appere_num[S[j]];
						}
					}
				}
			}
		}

		if (minNum == size_S + 1)
		{
			return "";
		}
		else
		{
			return S.substr(min_start, minNum + 1);
		}
	}
};

int _tmain(int argc, _TCHAR* argv[])
{
	Solution so;
	string S = "ADOBECODEBANC";
	string T = "ABC";
	string ret_str = so.minWindow(S, T);
	return 0;
}