40 lines
1.2 KiB
C++
40 lines
1.2 KiB
C++
/* Problem: https://leetcode.com/problems/permutation-in-string/ */
|
|
|
|
#include <iostream>
|
|
#include <unordered_map>
|
|
|
|
bool solution(const std::string s1, const std::string s2) {
|
|
if (s1.length() > s2.length())
|
|
return false;
|
|
std::size_t s1_len = s1.length();
|
|
std::unordered_map<char, std::size_t> s1_count, s2_substr_count;
|
|
for (const char c : s1)
|
|
s1_count[c]++;
|
|
for (auto c = s2.cbegin(), e = s2.cbegin() + s1.length(); c != e; c++) {
|
|
s2_substr_count[*c]++;
|
|
}
|
|
for (std::size_t i = s1_len, upto = s2.length(); i < upto; i++) {
|
|
bool match_found = true;
|
|
for (auto const [character, count] : s1_count) {
|
|
if (s2_substr_count[character] != count) {
|
|
match_found = false;
|
|
break;
|
|
}
|
|
}
|
|
if (match_found)
|
|
return true;
|
|
s2_substr_count[s2[i - s1_len]]--;
|
|
s2_substr_count[s2[i]]++;
|
|
}
|
|
for (auto const [character, count] : s1_count) {
|
|
if (s2_substr_count[character] != count)
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
int main() {
|
|
std::cout << solution("ab", "eidbaooo") << '\n'
|
|
<< solution("ab", "eidboaoo") << '\n'
|
|
<< solution("dinitrophenylhydrazine", "dimethylhydrazine") << '\n';
|
|
} |