The code below is an attempt at a solution to an exercise from the book "Cracking the Coding Interview."
I believe that the worst case time complexity of the code below is \$O(n)\$, where n is the length of each string (they should be the same length since I am checking if there lengths are equal) and the space complexity is \$O(n)\$.
Is this correct? In particular does checking the length of each string take \$O(1)\$ time?
def is_permutation(first_string, other_string):
if len(first_string) != len(other_string):
return False
count_first = {}
count_other = {}
for char in first_string:
if char in count_first.keys():
count_first[char] += 1
else:
count_first[char] = 1
for char in other_string:
if char in count_other.keys():
count_other[char] += 1
else:
count_other[char] = 1
for char in count_first.keys():
if char not in count_other.keys():
return False
elif count_first[char] != count_other[char]:
return False
return True
len()
might be more expensive than \$O(n)\$, and if it's \$O(n)\$ you don't need to worry about it. Your code must examine every character of both strings at least once, hence you no way can get better than \$O(n)\$, so the cost oflen()
doesn't matter in this context. \$\endgroup\$