4
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ I have rolled back the last edit. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Mathieu Guindon Apr 7 '17 at 16:43
  • \$\begingroup\$ Sorry about that. \$\endgroup\$ – invar Apr 7 '17 at 16:44
  • 4
    \$\begingroup\$ If xor is 0, strings are not necessarily permutations. Consider "aa" and "bb". \$\endgroup\$ – vnp Apr 7 '17 at 17:02
  • \$\begingroup\$ @vnp you're right. These aren't even proper solutions, then. \$\endgroup\$ – invar Apr 7 '17 at 17:05
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Eugene Lisitsky Apr 8 '17 at 17:46
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ And how would that intermediate value be used? How precisely would it get updated? Would it really be \$O(1)\$? \$\endgroup\$ – kyrill Apr 7 '17 at 20:02
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Eugene Lisitsky Apr 8 '17 at 17:39
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – kyrill Apr 8 '17 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.