3
\$\begingroup\$

Practicing for my interview, I am working on some problems in Python.

This problem is to decide two strings are permutation (or anagrams) of each each other.

def is_permutation(first, second):
    if len(first) != len(second):
        return False
    first_arr = [0 for i in range(256)] # ASCII size
    second_arr = [0 for i in range(256)] # ASCII size
    for i in range(len(first)):
        first_arr[ord(first[i])] += 1
        second_arr[ord(second[i])] += 1
    if first_arr != second_arr:
        return False
    else:
        return True

I feel this code can be more efficient, but I cannot make it. Can anybody give me advice or tip so that I can improve please?

\$\endgroup\$
0
3
\$\begingroup\$

The performance for the second line is \$O(1)\$, the fourth and fifth are \$O(256)\$ and your for loop on line six is \$O(n)\$. The code on line seven and eight are \$O(1)\$ and finally line nine is \$O(n)\$. Combining all this leads to \$O(1 + 256 + n (1 + 1) + n)\$, which simplify to \$O(n)\$.

The only time memory changes is on line four and five, where you use \$O(256)\$ more memory. And so this has \$O(1)\$ memory usage.

However, big O notation is just a guide. When you want to know what performs better test it.


If however you gave me this in an interview, I'd think you produce hard to read code. I would much prefer one of:

from collections import Counter


def is_permutation(first, second):
    return sorted(first) == sorted(second)


def is_permutation(first, second):
    return Counter(first) == Counter(second)

The former being \$O(n\log(n))\$ performance and \$O(n)\$ memory usage. The latter however is \$O(n)\$ in both performance and memory. 'Worse' than yours, but much easier to maintain.

\$\endgroup\$
0
3
\$\begingroup\$

From Sumit Raj's 2015 article 10 Neat Python Tricks Beginners Should Know, which I would classify as "more pythonic":

from collections import Counter
def is_anagram(str1, str2):
    return Counter(str1) == Counter(str2)
>>> is_anagram('abcd','dbca')
True
>>> is_anagram('abcd','dbaa')
False
\$\endgroup\$
1
  • \$\begingroup\$ It does seem like more pythonic! \$\endgroup\$
    – jayko03
    Jul 25 '17 at 1:27
2
\$\begingroup\$

You could improve your code a little bit by using just one array instead of two to count a balance between character populations in both strings:

    balance_arr = [0 for i in range(256)] # ASCII size
    for i in range(len(first)):
        balance_arr[ord(first[i])] += 1
        balance_arr[ord(second[i])] -= 1

Finally test if the array contains zeros only.

But it's still a character-level 'manual' operation.

\$\endgroup\$
0

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.