I need to implement a function to return True/false whether String A
contains String B. For example, String A = "This is a test"; String B =
"is is". So it will return TRUE if String A includes two "i" and two
"s". The function should also handle if String A and B have huge
values, like two big dictionary.
Because String B = "is is" (note the space), should the function return true
if String A contains two "i", two "s", one space?
The first step would be to parse String B so that we know to expect 2 "i", 2
"s", 1 " ".
What's the number of distinct chars? Is it A-Z and a-z for a total of 52?
If the number of distinct chars is small, say 256 distinct chars, create an
array, such as unsigned expect[256], to represent the number of chars to
expect. expect['i'] would equal 2, expect['s'] would equal 2, expect[' ']
would equal 1, and all other expect elements would be zero. If the number
of distinct chars is large, then you could use a map<char_type, unsigned> or
hashtable.
Now step through every char in String A. Let the char in question be char
c. Decrement expect[c] by one, but if it is zero then don't decrement it.
Now check if all the elements in expect are zero. As an optimization, you
only need to do this check if you decremented expect[c].
To check if all the elements in expect are zero, you could for example
create another array zero, such as unsigned zero[256] = {0}, and use memcmp
to compare expect to zero. There are other ways, maybe platform specific
ways that might be faster.
Remember to deal with the special case that String B is the empty string, in
which case you can probably immediately return true.
What's the best approach to achieve this with the best performance?
what's the Big O then?
My algorithm is O(length(String A)) + O(length(String B)).
I am thinking to put A and B into two hashtable, like key = "i" and
value = "2" and so on. Then compare these two hashtable. But how to
compare two hashtables? Please advise.
In principle it is doable, but putting all the chars of String A into a
hashtable might be rather expensive.
To compare two hashtables, you could iterate through the elements in the
first hash table, using a for_each(hash1.begin(), hash1.end()) structure, or
even for (Iter iter = hash1.begin(); iter != hash1.end(); ++iter). For each
element in hash1, look up the corresponding value in hash2, for example
hash2[iter->key]. Then check if the values are equal, for example
iter->value == hash2[iter->key].