At time 9min 4s, I am still not able to comprehend why you don't need to process every position. Appreciate it if you can elaborate more.

@prabhatjha7802

2 ай бұрын

Basically, in one process it starts at index "i" and goes through entire string taking the window size, basically (i, i + window_size), (i+word_size, i + word_size +window_size) and so on generally (i+k*word_size, i + k*word_size +window_size) for different possible values of k. Now, he is saying i just needs to be 0, 1, 2 in this example and in general case (0, 1, 2, . . . , word_size - 1). Why this would suffice is what you are asking right? Let me explain this way: Lets suppose your answer lies at some (i_0, i_0 + window_size), the in the run where you started at (i_0%word_size) would do, why as i_0 would be of the form (i+k*word_size, i + k*word_size +window_size) for i = i_0%word_size and k = i_0//word_size. Please think on this line and let me know if this make sense.

Sorry to say this , Little tricky to understand the explanation you have given.

Great vid, but leetcode wont accept it Time Limit Exceeded 179 / 179 testcases passed Testcases passed, but took too long.

@techdose4u

3 ай бұрын

Leetcode has given 3 seconds time limit for it. It will paas in 2900 ms approx. But yes, you can try some optimizations on string operations as used by top performers in submissions. This idea is same but code can be modified but this code makes life easier for someone new :)

@MrLeyt1125

3 ай бұрын

@@techdose4u I'm a newbie myself, your video helped me to understand algorithm. As far as I understand, the time is mainly spent on the copying operation curr = freq, so it’s faster to manually add and remove words from the curr dictionary. I stealed other code, very similar yo yours, it runs in 23 ms instead of 3sec: class Solution { public: vector findSubstring(string s, vector& words) { unordered_map dict_reference; //Эталонный словарь for (string& word: words) //Перебираю все слова в массиве words dict_reference[word]++; //Заполнение эталонного словаря (к его виду привожу текущий словарь каждую итерацию) int s_size = s.size(); //Длина s int word_size = words[0].size(); //длина words int words_count = words.size(); //кол-во words int window_size = word_size * words_count; //Размер sliding window vector result; //массив с ответами if (window_size > s_size or s.empty() or words.empty()) return result; for (int i = 0; i { unordered_map dictionary; //Текущий словарь int left = i; //Левый край sliding window int right = i; //Правый край sliding window int count = 0; //Счетчик найденных слов while (right + word_size dict_reference[word]) //Пока текущий словарь толще эталонного { string leftWord = s.substr(left, word_size); left += word_size; dictionary[leftWord]--; //Удаляем из него самое левое слово (то от которого уже уехало sliding window) count--; //Счетчик найденных слов -- } if (count == words_count) result.push_back(left); //Все слова найдены, добавляем ответ в результат } else { dictionary.clear(); //убиваем текущий словарь count = 0; left = right; } } } return result; } };

@kushagarsharma4783

29 күн бұрын

I wrote similar solution on my own 178/180 cases passed , that's why I am here😂