C++LeetCode 구현(30.모든 단 어 를 직렬 로 연결 하 는 하위 문자열)

Substring with Concatenation of All Words 모든 단어의 하위 문자열 을 연결 합 니 다.
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
Example 1:
Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.
Example 2:
Input:
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
Output: []
이 문 제 는 모든 단 어 를 연결 하 는 하위 문자열 을 구 합 니 다.즉,긴 문자열 을 정 하고 같은 길이 의 단 어 를 몇 개 더 정 해서 모든 단 어 를 연결 하 는 하위 문자열 의 시작 위 치 를 찾 는 것 이 어 려 운 문제 입 니 다.words 배열 에 n 개의 단어 가 있 고 모든 단어의 길이 가 len 이 라 고 가정 하면 실제 이 문 제 는 nxlen 길이 의 모든 하위 문자열 을 내 서 words 배열 의 모든 단어 로 구성 합 니 다.그러면 s 열 에 있 는 길이 가 len 인 하위 열 이 words 의 단어 인지 자주 판단 해 야 합 니 다.빠 른 판단 을 위해 HashMap 을 사용 할 수 있 습 니 다.또한 words 배열 에 중복 단어 가 있 을 수 있 기 때문에 HashMap 으로 모든 단어 와 그 출현 횟수 간 의 매 핑 을 만들어 야 합 니 다.즉,모든 단어 가 나타 난 횟수 를 통계 해 야 합 니 다.
s 의 모든 길이 가 nxlen 인 하위 문자열 을 옮 겨 다 니 며 나머지 하위 문자열 의 길이 가 nxlen 보다 작 을 때 더 이상 판단 할 필요 가 없습니다.그래서 i 는 0 부터(int)s.size()-nxlen 까지 끝나 면 됩 니 다.여기 서 반드시 s.size()를 정형 수로 바 꾸 고 해법 을 해 야 합 니 다.반드시 이러한 습관 을 형성 해 야 한다.size()뒤에 숫자 를 빼 려 고 할 때 먼저 int 형 으로 바 꿔 야 한다.size()의 반환 값 은 기호 형 이 없 기 때문에 자신 보다 큰 숫자 를 빼 면 오류 가 발생 할 수 있다.옮 겨 다 니 는 길이 가 nxlen 인 하위 문자열 에 대해 서 는 words 의 모든 단어 로 구성 되 어 있 는 지 검증 해 야 합 니 다.검사 방법 은 매번 길이 가 len 인 하위 문자열 을 가 져 와 words 의 단어 인지 확인 하 는 것 입 니 다.비 교 를 편리 하 게 하기 위해 다른 HashMap 을 만 듭 니 다.꺼 낸 단어 가 words 에 없 으 면 break 합 니 다.그렇지 않 으 면 새로운 HashMap 에 있 는 맵 값 에 1 을 추가 하고 맵 값 이 원래 HashMap 의 맵 값 을 초과 하면 break 합 니 다.현재 단어 가 words 에 있 더 라 도 words 의 횟수 를 초과 하면마음 에 안 들 어.for 순환 밖에서 만약 에 j 가 n 과 같다 면 검 측 된 n 개의 길이 가 len 인 하위 문자열 은 모두 words 중의 단어 이 고 words 를 구성 하면 현재 위치 i 를 결과 res 에 추가 하면 됩 니 다.구체 적 인 참조 코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        if (s.empty() || words.empty()) return {};
        vector<int> res;
        int n = words.size(), len = words[0].size();
        unordered_map<string, int> wordCnt;
        for (auto &word : words) ++wordCnt[word];
        for (int i = 0; i <= (int)s.size() - n * len; ++i) {
            unordered_map<string, int> strCnt;
            int j = 0; 
            for (j = 0; j < n; ++j) {
                string t = s.substr(i + j * len, len);
                if (!wordCnt.count(t)) break;
                ++strCnt[t];
                if (strCnt[t] > wordCnt[t]) break;
            }
            if (j == n) res.push_back(i);
        }
        return res;
    }
};

이 문 제 는 O(n)시간 복잡 도의 해법 도 있 는데 디자인 사고 가 매우 교묘 하지만 생각 하기 어렵다.블 로 거들 의 눈대중 은 아직 이런 수준 에 이 르 지 못 했다.이 방법 은 한 글자 한 글자 옮 겨 다 니 는 것 이 아니 라 한 단어 한 단어의 옮 겨 다 니 는 것 입 니 다.예 를 들 어 제목 의 예 에 따 르 면 문자열 s 의 길이 n 은 18 이 고 words 배열 에는 두 단어(cnct=2)가 있 습 니 다.각 단어의 길이 len 은 모두 3 입 니 다.그러면 옮 겨 다 니 는 순 서 는 0,3,6,8,12,15 입 니 다.그리고 한 글자 1,4,7,9,13,16 입 니 다.그리고 한 글자 더 옮 겨 주세요.2,5,8,10,14,17.그러면 모든 상황 을 옮 길 수 있 습 니 다.아니면 한 글자 로 할 까요? HashMap m1 은 words 의 모든 단 어 를 기록 한 다음 0 부터 옮 겨 다 니 며 왼쪽 경계 위 치 를 left 로 기록 합 니 다.count 는 현재 일치 하 는 단어의 개 수 를 표시 합 니 다.그리고 한 단어,한 단어의 옮 겨 다 니 기,현재 옮 겨 다 니 는 단어 t 가 m1 에 존재 한다 면 다른 단어 에 추가 합 니 다. HashMap m2 에서 m2 의 개수 가 m1 의 개수 보다 작 으 면 count 는 1 을 증가 하고 크 면 처 리 를 해 야 합 니 다.예 를 들 어 다음 과 같은 경우:s=barfoo,words={bar,foo,abc}은 words 에 abc 를 추가 하 였 습 니 다.그 목적 은 barfoo 가 멈 추 지 않 고 두 번 째 foo 를 옮 겨 다 닐 때,  m2[foo]=2,이때 m1[foo]=1,이 때 는 연속 되 지 않 기 때문에 왼쪽 경계 left 의 위 치 를 이동 하려 면 먼저 첫 번 째 단어 t1=bar 를 꺼 낸 다음 m2[t1]를 1 로 줄 여야 합 니 다.이때 m2[t1]해법 2:

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        if (s.empty() || words.empty()) return {};
        vector<int> res;
        int n = s.size(), cnt = words.size(), len = words[0].size();
        unordered_map<string, int> m1;
        for (string w : words) ++m1[w];
        for (int i = 0; i < len; ++i) {
            int left = i, count = 0;
            unordered_map<string, int> m2;
            for (int j = i; j <= n - len; j += len) {
                string t = s.substr(j, len);
                if (m1.count(t)) {
                    ++m2[t];
                    if (m2[t] <= m1[t]) {
                        ++count;
                    } else {
                        while (m2[t] > m1[t]) {
                            string t1 = s.substr(left, len);
                            --m2[t1];
                            if (m2[t1] < m1[t1]) --count;
                            left += len;
                        }
                    }
                    if (count == cnt) {
                        res.push_back(left);
                        --m2[s.substr(left, len)];
                        --count;
                        left += len;
                    }
                } else {
                    m2.clear();
                    count = 0;
                    left = j + len;
                }
            }
        }
        return res;
    }
};

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