Say you are given two strings A and B where size(A)>size(B). You have to find
in O(n) time if all the characters in B appear in A as well. Repetitions are not
to be considered
example: string A:google string B:log answer:true
string A:google string B:fog answer:false
string A:google string B:lol answer:true
P.S. try and use minimum space...
Octofinder
Subscribe to:
Post Comments (Atom)
bool IfSuperSet(B,A)
ReplyDelete1. make BitMap of all the chars possible in B
2. for i = 0 to length[B]
3. do if(BitMap[B[i]] == 0)
4. then BitMap[B[i]] = 1;
5. for i = 0 to length[A]
6. do if(BitMap[A[i]] == 1)
7. then BitMap[A[i]] = 0;
8. return (BitMap == 0);
I guess hashing will do it........but hash table will be of six=ze 26........so space will be used.......time will be O(n).....
ReplyDelete