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.
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.
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 :)
@@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; } };
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 //................................................................
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.
That's genius bro. I was stuck on that case only.
Bro thanks , you are the leetcode pro , i will gift you leetcode premium. Thaks so much. I was stuck since 2 months . thanks bro.
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.
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.
Great vid, but leetcode wont accept it
Time Limit Exceeded
179 / 179 testcases passed
Testcases passed, but took too long.
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 :)
@@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;
}
};
I wrote similar solution on my own 178/180 cases passed , that's why I am here😂
Sorry to say this , Little tricky to understand the explanation you have given.
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
//................................................................
to be honest, explanation can be improved.