Checking whether one string is a permutation of another

Question

I solved the standard "write a method to determine if one string is a permutation of the other" question with the following code, using xor, map, and reduce:

from functools import reduce
from operator import xor
def checkPermutation(str1, str2):
 return not bool(reduce(xor, map(ord, str1 + str2)))

The idea is that if the two strings are permutations, the xor sum of the int value of every character of the concatenation of the two strings must be 0.

If I write the algorithm out by hand it seems come down to O(n) time and space:

def checkPermutation(str1, str2):
 # map every character in the strings to its integer value
 map = []
 str = str1 + str2
 for char in str:
 map.append(ord(char))
 # xor every number that was mapped into a sum
 sum = map[0]
 for i in range(1, len(map)):
 sum ^= map[i]
 return not bool(sum)

Essentially I think that's what reduce and map are doing but depending on how they're actually implemented in python, the time and space complexity of two solutions may differ.

• Mathieu Guindon: I have rolled back the last edit. Please see what you may and may not do after receiving answers .
• invar: Sorry about that.
• vnp: If xor is 0, strings are not necessarily permutations. Consider "aa" and "bb".
• invar: @vnp you're right. These aren't even proper solutions, then.
• Eugene Lisitsky: xor is not enough to be sure. The only thing you can say, if xor(a) != xor(b) then string aren't permutations. If they are equal, you can't say nothing definitely.

Answer 1

For both strings, generate a dictionary containing distinct characters of the string as keys and their respective counts as values.

If the two dictionaries are equal, the strings are permutations of each other.

Instead of manually counting characters using a dict, you can utilize the collections.Counter class. To save time in case the strings are of different length, you can compare their lengths first.

from collections import Counter
def checkPermutation(str1, str2):
 return len(str1) == len(str2) and Counter(str1) == Counter(str2)

This is a \$O(n)\$ time and approximately \$O(1)\$ space solution. Approximately because – presumably – the less distinct characters there are in the input strings, the less space is occupied by the counters.

Answer 2

I guess it will be O(n) in time, because you are stepping through the whole line and with n elements. And this is the best case.

But it can be O(1) in space because you need only room to store original line and an intermediate value which gets updated with every symbol in the line.

• kyrill: And how would that intermediate value be used? How precisely would it get updated? Would it really be \$O(1)\$?
• Eugene Lisitsky: Just like topic starter stated above: for el in s: sum ^= el . It requies n steps to be done, and only sizeof(el) bytes to be stored.
• kyrill: Yes, you could compute hashes first, and only if the hashes match you compare the strings. In worst case, you'll read the strings twice, but average performance would be improved.