IsPermutation

This is from the Udemy course “Data Structures and Algorithms bootcamp”.

Are the two input strings a permutation of each other? You are given these unit tests:

You can sort both strings, or character arrays, and then if they are permutations of each other they will equal one another. This will run in O(nlog(n)) time complexity, due to the sort being used. This technique will work with a mixture of lower and upper case characters.

If you have simple words that don’t contain many duplicated characters, such as most English words, you might be able to use a bit mask to cache the characters in the words. The mask won’t be aware of the numbers of individual characters, and so the ‘solution’ below will fail with words like “aaab” and “bbba”.

Every character is within the range 0,n,25. Hence a 32 bit int will do. If we shift ‘1’ by the numeric value of the char, inclusive or it with a mask, and do that for both strings, then permutations will equal each other. The strings will need to match each other in length, so if they don’t that is a given they are not permutations.

This technique will work with upper or lower characters, but not a mixture. To make it work with a mixture, you can add two more masks, so that there is a mask for upper and a mask for lower case chars for each string. Then the upper masks should equal each other, as should the lower masks.

Leave a Reply

Your email address will not be published.