C++LeetCode 구현(76.최소 창 하위 문자열)

[LeetCode]76.최소 창 하위 문자열 최소 창 하위 문자열
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).
Example:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Note:

If there is no such window in S that covers all characters in T, return the empty string  "" .

If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

이 문 제 는 원래 문자열 S 와 목표 문자열 T 를 주 었 습 니 다.S 에서 가장 짧 은 하위 문자열 을 찾 아 T 의 모든 자 모 를 포함 하고 시간 복잡 도 를 O(n)로 제한 합 니 다.이 문제 의 요 구 는 O(n)의 시간 도 에서 이 최소 창 문자열 을 찾 는 것 입 니 다.폭력 검색 Brute Force 는 사용 할 수 없습니다.모든 하위 문자열 을 옮 겨 다 니 는 시간 복잡 도 는 제곱 급 이기 때 문 입 니 다.그러면 생각해 보 세 요.시간 복잡 도가 이렇게 엄격 하 다 는 것 은 한 번 에 임 무 를 완성 해 야 한 다 는 것 을 설명 합 니 다.물론 몇 번 을 옮 겨 다 니 는 것 도 O(n)이지 만 꼭 필요 한 것 은 아 닙 니 다.한 번 에 옮 겨 다 니 며 잡 으 려 고 합 니 다!그러면 다시 생각해 보 자.T 에 있 는 모든 자 모 를 포함 하려 면 T 에 있 는 모든 자모 에 대해 서브 꼬치 에 있 는 지 빨리 찾 아야 한다.총 시간 이 O(n)에 걸 렸 으 니 여기 서 시간 을 낭비 하고 싶 지 않 을 것 이다.공간 으로 시간 을 바 꾸 자.동쪽 을 바라 보 니 시간 이 네요 T.T).HashMap 을 사용 하여 T 의 모든 자모 와 나타 나 는 횟수 사이 의 매 핑 을 만 듭 니 다.그러면 의문 이 생 길 수 있 습 니 다.왜 HashSet 을 사용 하지 않 는 지,서 두 르 지 마 세 요.뒤에서 HashMap 을 사용 하 는 것 이 얼마나 좋 은 지 알 수 있 습 니 다.정말 절묘 합 니 다~
현재 머 릿 속 에 풀이 가득 한 상황 에서 우 리 는 간단 한 예 로 분석 합 시다.문제 의 예 에서 S 가 좀 길 고 짧 은 S="ADBANC",T="ABC"로 바 꾸 면 육안 으로 S 를 한 번 훑 어 보 는 것 이 좋 습 니 다.먼저 첫 번 째 는 A,응,좋아,T 중 에 있어,두 번 째 는 D,T 중 에 없어,무시 하고 세 번 째 는 B,응,좋아,T 중 에 있어,네 번 째 는 A,하나 가 많아 졌 습 니 다.예 를 많이 하 는 사람 이 이상 하지 않 습 니까?받 으 세 요.다섯 번 째 는 N 입 니 다.시원 하 게 갑 니 다.여섯 번 째 는 C 입 니 다.그러면 S 꼬치 전체 가 필요 할 것 같 습 니 다.사실은 그렇지 않 습 니 다.주의 하기 전에 A 가 하나 더 있 습 니 다.첫 번 째 A 를 없 애 도 괜 찮 습 니 다.네 번 째 A 는 대체 할 수 있 고 두 번 째 D 도 없 기 때 문 입 니 다.T 꼬치 에 없 으 면 세 번 째 B 는 더 이상 없 을 것 입 니 다.그렇지 않 으 면 B 가 없습니다.그래서 최종 답 은'BANC'다.위의 설명 을 통 해 당신 은 재 미 있 는 현상 을 발견 한 적 이 있 습 니까?먼저 확장 하고 수축 합 니 다.마치 하나의 창 처럼 오른쪽 경 계 를 확대 한 다음 에 왼쪽 경 계 를 수축 합 니 다.위의 예 에서 오른쪽 경 계 를 확대 하지 못 한 후에 왼쪽 경 계 를 수축 하기 시 작 했 습 니 다.사실은 복잡 한 예 에 대해 오른쪽 경 계 를 확대 한 다음 에 왼쪽 경 계 를 축소 할 수 있 습 니 다.그리고 오른쪽 경 계 를 넓 히 는 등이것 은 마치 끊임없이 미 끄 러 지 는 창 과 같 습 니 다.이것 이 바로 유명한 미끄럼 창 Sliding Window 입 니 다.정말 신기 입 니 다.여러 개의 문자열,하위 배열,하위 서열 등 문 제 를 풀 수 있 습 니 다.반드시 능숙 하 게 파악 해 야 합 니 다!
다음은 코드 로 이 루어 지 는 것 을 고려 해 보 겠 습 니 다.먼저 앞 에 묻 힌 복선 에 답 하 겠 습 니 다.왜 HashMap 을 사용 해 야 하 는 지,HashSet 이 아 닌 HashMap 을 사용 해 야 하 는 지 알 수 있 을 것 입 니 다.T 꼬치 에 있 는 알파벳 의 개 수 를 집계 해 야 하기 때 문 입 니 다.T 꼬치 에 있 는 알파벳 만 보 는 것 이 아 닙 니 다.T 열 에 있 는 자모의 개 수 를 집계 한 후에 S 열 을 옮 겨 다 니 기 시 작 했 습 니 다.S 에 있 는 모든 자모 에 대해 HashMap 에서 매 핑 값 을 1 로 줄 였 습 니 다.1 을 줄 인 후에 도 매 핑 값 이 0 보다 크 면 현재 옮 겨 다 니 는 자 모 는 T 열 에 있 는 자모 임 을 나타 내 고 하나의 카운터 cnct 를 사용 하여 1 을 증가 시 킵 니 다.cnct 와 T 문자열 의 자모의 개수 가 같 을 때 이 창 은 T 문자열 의 모든 자 모 를 포함 하고 있 음 을 설명 합 니 다.이때 minLen 과 결과 res 를 업데이트 합 니 다.여기 있 는 minLen 은 전체 변수 로 T 문자열 의 모든 자 모 를 포함 하 는 가장 짧 은 문자열 의 길 이 를 기록 합 니 다.결 과 res 는 이 가장 짧 은 문자열 입 니 다.그 다음 에 왼쪽 경 계 를 수축 하기 시 작 했 습 니 다.옮 겨 다 닐 때 맵 값 이 1 을 줄 였 기 때문에 이 때 자 모 를 제거 할 때 뺀 1 을 다시 추가 해 야 합 니 다.이때 1 을 추가 한 값 이 0 보다 크 면 T 중의 자모 가 하나 빠 졌 다 는 것 을 의미 합 니 다.그러면 cnct 값 은 1 을 줄 이 고 왼쪽 경 계 를 왼쪽으로 이동 해 야 합 니 다.T 꼬치 에 없 는 알파벳 에 대한 매 핑 값 도 이렇게 늘 리 고 줄 이 는 거 야?정말 대장부 야?사실 별일 없어 요.T 열 에 없 는 알파벳 에 대해 서 는 1 을 줄 인 후에-1 로 변 하면 cnct 가 증가 하지 않 아 요.그 후에 왼쪽 경 계 를 수축 할 때 맵 값 이 1 을 더 하면 0 이 되 고 cnct 도 감소 하지 않 기 때문에 아무런 영향 이 없어 요.다음은 구체 적 인 절차 입 니 다.
-T 를 한 번 스 캔 하고 해당 하 는 문자 와 나타 나 는 횟수 를 HashMap 에 저장 합 니 다.
-그리고 S 를 옮 겨 다 니 기 시작 하면 옮 겨 다 니 는 알파벳 에 대응 하 는 HashMap 의 value 를 1 로 줄 이 고 1 을 줄 인 후에 도 0 보다 크 면 cnct 는 1 을 증가 합 니 다.
-cnct 가 T 문자열 길이 와 같 을 때 순환 을 시작 하여 하나의 문자열 을 기록 하고 최소 문자열 값 을 업데이트 합 니 다.그 다음 에 하위 창의 왼쪽 경 계 를 오른쪽으로 이동 합 니 다.만약 에 제 거 된 자모 가 T 열 에 없어 서 는 안 될 자모 라면 cnct 는 1 을 줄 이 고 이때 T 열 이 완전히 일치 하지 않 음 을 나타 냅 니 다.
해법 1:

class Solution {
public:
    string minWindow(string s, string t) {
        string res = "";
        unordered_map<char, int> letterCnt;
        int left = 0, cnt = 0, minLen = INT_MAX;
        for (char c : t) ++letterCnt[c];
        for (int i = 0; i < s.size(); ++i) {
            if (--letterCnt[s[i]] >= 0) ++cnt;
            while (cnt == t.size()) {
                if (minLen > i - left + 1) {
                    minLen = i - left + 1;
                    res = s.substr(left, minLen);
                }
                if (++letterCnt[s[left]] > 0) --cnt;
                ++left;
            }
        }
        return res;
    }
};

이 문 제 는 HashMap 을 사용 하지 않 고 int 의 배열 로 대체 할 수 있 습 니 다.ASCII 는 256 글자 만 있 기 때문에 크기 가 256 인 int 배열 로 HashMap 을 대체 할 수 있 습 니 다.그러나 보통 알파벳 문자열 을 입력 하 는 문 자 는 128 개 밖 에 없 기 때문에 128 개 만 사용 할 수 있 습 니 다.나머지 부분의 사 고 는 똑 같 습 니 다.하나의 데이터 구조 만 바 꾸 었 지만하지만 운행 속도 가 배로 높 아 졌 다 는 것 은 해시 맵 보다 배열 이 빠르다 는 뜻 이다.또한 더욱 최적화 할 수 있다.매번 하위 문자열 을 계산 할 필요 가 없다.시작 위치 와 길이 만 있 으 면 유일 하 게 하위 문자열 을 확정 할 수 있다.최종 결과 하위 문자열 의 시작 위 치 를 기록 하기 위해 전역 변수 인 minLeft 를 사용 합 니 다.-1 로 초기 화하 고 최종 적 으로 minLen 과 결합 하면 최종 결 과 를 얻 을 수 있 습 니 다.되 돌아 갈 때 minLeft 가 초기 값-1 이면 빈 문자열 로 돌아 가 야 합 니 다.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> letterCnt(128, 0);
        int left = 0, cnt = 0, minLeft = -1, minLen = INT_MAX;
        for (char c : t) ++letterCnt[c];
        for (int i = 0; i < s.size(); ++i) {
            if (--letterCnt[s[i]] >= 0) ++cnt;
            while (cnt == t.size()) {
                if (minLen > i - left + 1) {
                    minLen = i - left + 1;
                    minLeft = left;
                }
                if (++letterCnt[s[left]] > 0) --cnt;
                ++left;
            }
        }
        return minLeft == -1 ? "" : s.substr(minLeft, minLen);
    }
};

C++구현 LeetCode(76.최소 창 하위 문자열)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 최소 창 하위 문자열 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부탁드립니다!