[LeetCode] 76. Minimum Window Substring

문제 URL : https://leetcode.com/problems/minimum-window-substring/

Minimum Window Substring - LeetCode

 

문제 접근법 : 

 

투포인터 + hashmap(c++ -> unordered_map)을 이용한 문제입니다. 

s의 substring중  길이가 가장 짧으면서 t의 원소의 개수를 완전히 포함하는 substring을 구하면됩니다.

즉 무슨말이냐면

s가 abcbeabba 일때 t가 aba 라면 

문자열 t가 a를 2개갖고있고 b를 한개 갖을테니

 

s의 substring중 0번째 인덱스에서 길이가 6인  abcbea 와

5번째 인덱스에서 길이가 4인 abba 2개입니다.

 

길이가 6인 abcbea 는 a가 2개 , b가 2개 c가1개 e가1개  다른것이 있어도 상관없습니다. t는 a가 2개이고 b가 1개이니 

a가 2개이상이고 b가 1개이상이기만하면 minimun window substring입니다. 이관계가 성립하면 길이가 6인것이 성립하고

 

5번째 인덱스에서 길이가 4인 abba는 a가 2개고 b가 2개이니 t가 가지고있는것을 전부 만족합니다.

 

갖고있는 수의 자료를 알아보기위해서는 map을 이용하면 편리하고 어떻게 투포인터를 이용하냐?

 

m1,m2를 맵이라고하고 m2는 t의 문자열개수를 가지고있는 맵이고

m1은 s의 substring의 문자열을 갖는 맵일때

i=0부터 i<s.size()를 돌면서

m1[s[i]]를 넣으면서

m1이 m2를 전부 포함하는지 확인 하면됩니다.

 

소스코드 :

class Solution {
public:
bool issame(unordered_map<char,int> &m1,unordered_map<char,int> &m2){
	for(auto it:m2){
		if(m1[it.first]<it.second)return false;
	}
	return true;
}
string minWindow(string s, string t) {
	if(s.size()<t.size())return "";
	unordered_map<char,int> m1,m2;
	for(char c: t)m2[c]++;
	int Min=1e8;
	int l=0;
	int left =0;
	for(int i=0;i<s.size();i++){
		if(m2.count(s[i])==0)continue;
		m1[s[i]]++;
		while(m1.size()==m2.size()&&issame(m1,m2)){
			if(i-l+1<Min){
				Min = i-l+1;
				left=l;
			}
			if(m1.count(s[l])){
				m1[s[l]]--;
				if(m1[s[l]]==0)
					m1.erase(s[l]);
			}
			l++;
		}
	}
	if(Min==1e8) return "";	
	return s.substr(left,Min);        
}
};

 

 

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.