One way to optimize this implementation is to store all already checked substrings in input S against there evaluation output matched/not matched. If the same substring comes up again later for matching then we can avoid processing it on the basis of the stored matched/not matched value. If matched then current substring will also match. If not matched then current will not match. It will help us bypass the testcase of S = "aaaaa.....aaaa" of length 10000 and words = {"a", "a", ... "a"} of length = 5000. It will increase memory usage but help to optimize on latency.
@enigma288628 күн бұрын
That's genius bro. I was stuck on that case only.
@KushagraJain-fc3nt24 күн бұрын
Bro thanks , you are the leetcode pro , i will gift you leetcode premium. Thaks so much. I was stuck since 2 months . thanks bro.
@ahyungrocks55094 ай бұрын
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.
@prabhatjha78024 ай бұрын
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.
@madhavilathakarumanchi71002 ай бұрын
Sorry to say this , Little tricky to understand the explanation you have given.
@MrLeyt11255 ай бұрын
Great vid, but leetcode wont accept it Time Limit Exceeded 179 / 179 testcases passed Testcases passed, but took too long.
@techdose4u5 ай бұрын
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 :)
@MrLeyt11255 ай бұрын
@@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 < word_size; i++) //Перебор всех стартовых позиций (проходим s words[0].size раз) { 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; } };
@kushagarsharma47832 ай бұрын
I wrote similar solution on my own 178/180 cases passed , that's why I am here😂
@harsha17126 күн бұрын
java code explained the same way ,not my sol class Solution { public List findSubstring(String s, String[] words) { List ans = new ArrayList(); int n = s.length(); int m = words.length; int w = words[0].length(); HashMap map = new HashMap(); for(String x : words) map.put(x, map.getOrDefault(x,0)+1); for(int i=0; i 1) ? b - 1 : null); count--; k=k+w; } }//inner for loop }//outer for loop return ans; }//method }//class //................................................................