[LeetCode]Substring with Concatenation of All Words-白红宇

[LeetCode]Substring with Concatenation of All Words

阅读量：4150 次

发布时间：2019-05-25

本文共 2100 字，大约阅读时间需要 7 分钟。

class Solution {//because all the word have same length, if they do not have the same length then they can not be solve by //the solution below//so it can be solve by iterating finding the substring in the input stringpublic:	vector
   
     findSubstring(string S, vector
    
      &L) {		map
     
       words;//record words, to find if the substring is in the words		map
      
        curStr;//keep record of the occurrence time of every word		for(int i = 0; i < L.size(); ++i)			++words[L.at(i)];		int N = L.size();		vector
       
         ret;		if(N <= 0)	return ret;		int M = L.at(0).size();		for(int i = 0; i <= (int)S.size()-N*M; ++i)		{			curStr.clear();			int j = 0;			for(j = 0; j < N; ++j)			{				string w = S.substr(i+j*M, M);				if(words.find(w) == words.end())					break;				++curStr[w];				if(curStr[w] > words[w])					break;			}			if(j == N)	ret.push_back(i);		}		return ret;	}};

second time

class Solution {public:    vector
   
     findSubstring(string S, vector
    
      &L) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        if(L.size() == 0) return vector
     
      ();        int wordLen = L[0].size();        int wordNum = L.size();        int wordsLen = wordLen*wordNum;        vector
      
        ans;                map
       
         wordMap;        for(int i = 0; i < L.size(); ++i)        {            if(wordMap.find(L[i]) == wordMap.end())                wordMap[L[i]] = 1;            else wordMap[L[i]]++;        }                for(int i = 0; i < S.size(); ++i)        {            int j = wordsLen-1+i;            if(j < S.size())            {                map
        
          curWordMap; bool flag = true; for(int k = i, curWordNum = 0; curWordNum < wordNum; k += wordLen, curWordNum++) { string tmpStr = S.substr(k, wordLen); if(curWordMap.find(tmpStr) == curWordMap.end()) curWordMap[tmpStr] = 1; else curWordMap[tmpStr]++; if(wordMap.find(tmpStr) == wordMap.end() || curWordMap[tmpStr] > wordMap[tmpStr]) { flag = false; break; } } if(flag) ans.push_back(i); } } return ans; }};