current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 5 down vote favorite

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
share|improve this question
    
Have you tested this code? – 200_success♦ Sep 8 at 1:31
    
Yes, I have tested it. – newToProgramming Sep 8 at 1:34
3  
I have a hard time believing that. It's very obviously wrong. – 200_success♦ Sep 8 at 1:36
1  
I edited the code, and re-tested it. – newToProgramming Sep 8 at 1:48
up vote 14 down vote accepted

Yes, len(str) should be O(1) in Python. (Good question!) Each of your for loops is O(n), so your whole function is O(n).

Your counting loops could be written more compactly as

for char in first_string:
    count_first[char] = 1 + count_first.get(char, 0)

The epilogue could be simplified to

return count_first == count_other

It pays to get familiar with the standard Python library, though. Your entire function could be more simply implemented as

from collections import Counter

def is_permutation(a, b):
    return len(a) == len(b) and Counter(a) == Counter(b)

… where len(a) == len(b) is an optional optimization. Writing less code simplifies maintenance and tends to create fewer opportunities for introducing bugs (as in Rev 2 of your question).

share|improve this answer
3  
"Writing less code simplifies maintenance and tends to create fewer opportunities for introducing bugs": Come over to code golf and you'll get some great tips on how to simplify maintenance. ;-P – Stewie Griffin Sep 9 at 7:29
    
codegolf.stackexchange.com :D – mbomb007 Sep 9 at 14:46
2  
Let's not get carried away here. There's a reason why I wrote "less code" instead of "shorter code", and included "tends to"! – 200_success♦ Sep 9 at 14:49
up vote 4 down vote

What I understand is that you want to know if 2 strings contain the same characters in the same quantity and not necessarily arranged similarly.

For example "cat" and "act" should return true.

You could check the length, then sort both strings and just compare them using ==.

share|improve this answer
2  
ideone.com/7sIoF4 Is this kind of implementation what you were talking about? Not sure about the big O notation in this example. I believe sort is O(n log n) – N.J.Dawson Sep 8 at 9:56
2  
Yes, it's O(n log n), so less efficient even if more compact to write. – Quentin Pradet Sep 8 at 10:07
2  
In practice, lots of Python code tends to be slow (by a constant factor), and dict operations can also be slow (by a constant factor), so the O(n log n) solution with a small constant factor can be faster than the O(n) solution. To figure out which one is faster for you, benchmark it for your typical inputs. Without the benchmark I'd go with the short solution sorted(a) == sorted(b), because it's easier to understand what it does and that it's correct. – pts Sep 8 at 12:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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