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.

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.