Checking if two strings are permutations (anagrams) in Python

Question

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?

Peilonrayz · Accepted Answer · 2017-07-24 22:31:39Z

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.

Ralph · Accepted Answer · 2017-07-24 22:27:31Z

3

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

answered Jul 24, 2017 at 22:27

Ralph

311 bronze badge

\$\begingroup\$ It does seem like more pythonic! \$\endgroup\$

jayko03
– jayko03

2017-07-25 01:27:41 +00:00
Commented Jul 25, 2017 at 1:27

Add a comment |

CiaPan · Accepted Answer · 2017-07-25 07:57:05Z

2

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.

answered Jul 25, 2017 at 7:57

CiaPan

1,9261 gold badge12 silver badges17 bronze badges

Add a comment |

Stack Exchange Network

Checking if two strings are permutations (anagrams) in Python

3 Answers 3

You must log in to answer this question.

Hot Network Questions

Checking if two strings are permutations (anagrams) in Python

3 Answers 3

You must log in to answer this question.

Related

Hot Network Questions