[OJ.leetcode] substring-with-concatenation-of-all-words

https://oj.leetcode.com/problems/substring-with-concatenation-of-all-words/

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

//hint : no order //the same length /* extra memory? Yes L includes unique strings only? No 풀이 : L로 dictionary를 만들고 S를 처음부터 순회하면서 dictionary에 있는 단어인지를 체크해나가기 시간복잡도 : O(s*l) s: S의 길이, l: L의 길이 공간복잡도 : O(2l) dictionary size*2(sub의 max가 dictionary 이므로) 주의점 : 집합 L의 string끼리 concate 되었을때 또다른 L의 string이 포함될 수 있음 : L= ab,cd,bc,df S= abcdfabcd 의 경우. TLE : 첫 시도에 시간초과, 핵심은 dictionary에 있는 단어들이 딱 "한번" 씩만 포함되어야하므로 once check를 해줘서 가지치기를 하는 것. */ class Solution { public: vector<int> findSubstring(string S, vector<string> &L) { unordered_map<string,int> dictionary; unordered_map<string,int> sub; vector<int> res; bool isSubstring = true; int wordLength = L[0].size(); if(S.size() <= 0 || S.size() < L.size()*wordLength ) return res; for(int i=0; i< L.size() ; i++) { ++dictionary[L[i]]; } for(int i=0; i<=(S.size()-wordLength*L.size()) ; ++i) { isSubstring = true; sub.clear(); if (dictionary.find(S.substr(i,wordLength)) != dictionary.end() ) { for(int k=0 ; k<L.size() ; ++k){ string nextWord = S.substr(i+k*wordLength, wordLength); if(dictionary.find(nextWord) == dictionary.end()) { isSubstring = false; break; } else { //duplication check ++sub[nextWord]; if(sub[nextWord] > dictionary[nextWord]) { isSubstring = false; break; } } } if(isSubstring == true) { res.push_back(i); } } } return res; } };