Back to course home
0% completed
Vote For New Content
Alternate C++ solution -- 2 maps
Roberto Pantoja
Jun 15, 2023
Use two maps - one holds char freq. of pattern, the other holds char freq. of current window.
static bool findPermutation(const string &str, const string &pattern) { unordered_map<char, int> pattern_map; unordered_map<char, int> string_map; int K = pattern.size(), start = 0; for(char c : pattern) pattern_map[c]++; for(int end = 0; end < str.size(); end++){ string_map[str.at(end)]++; if(end > K - 1){ string_map[str.at(start)]--; if(string_map[str.at(start)] <= 0) string_map.erase(str.at(start)); start++; } if(string_map == pattern_map) return true; } return false; }
If at any point both maps are the same, we have found the permutation.
The added map adds some space complexity, but I find this solution much easier to follow.
0
0
Comments
Comments
On this page