Do not use std::map
. Usually it has O(log N)
write, and O(log N)
access. And malloc call on write.
For char
you can use simple int freq[256]
table (or std::vector
if you are so inclined).
bool stringExists(const string& word, const string& cont) {
int freq[CHAR_MAX-CHAR_MIN+1]={0};
for (int c: cont) ++freq[c-CHAR_MIN];
for (int c: word) if(--freq[c-CHAR_MIN]<0) return false;
return true;
}
Complexity of this code is O(N + M)
, where N
and M
are: word.size()
and cont.size()
. And I would guess that it is at least 100 times faster even from small sized inputs.