November 20, 2010

Say you have one string of alphabetic characters, and say you have another, guaranteed smaller string of alphabetic characters. Algorithmically speaking, what’s the fastest way to find out if all the characters in the smaller string are in the larger string?

What if – given that we have a limited range of possible characters – I assigned each character of the alphabet to a prime number starting with 2 and going up from there. So A would be 2, and B would be 3, and C would be 5, etc. And then I went through the first string and ‘multiplied’ each character’s prime number together. You’d end up with some big number right? And then – what if I iterated through the 2nd string and ‘divided’ by every character in there. If any division gave a remainder – you knew you didn’t have a match. If there was no remainders through the whole process, you knew you had a subset.

%d bloggers like this: