Determining if a word is an anagram of another

Question

The question was to see if a word is an anagram of another word.

How would you improve this? It returns True if an anagram, or False otherwise.

# write the function is_anagram
def is_anagram(test, original):
    if len(test) != len(original):
        return False
    for letter in test.lower():
        if letter not in original.lower():
            return False
    for letter in original.lower():
        if letter not in test.lower():
            return False
    return True

Answer 1

The collections module provides a Counter class that can do the counting and the comparing for you:

from collections import Counter
>>> Counter('nana') == Counter('anna')
True
>>> Counter('nana') == Counter('ana')
False

Counter is basically a dictionary with items as keys and counts as values, so you can build it yourself from more primitive Python types by doing something like:

def count_items(sequence):
    counts = {}
    for item in sequence:
        counts[item] = counts.get(item, 0) + 1
    return counts

def is_anagram(a, b):
    return count_items(a.lower()) == count_items(b.lower())

Answer 2

You need to check if each letter occurs the name number of times in both strings.

One method would be to sort the letters and compare the lists of letters for equality.

Here is my approach:

def is_anagram(test, original):
  return sorted(list(test.lower())) == sorted(list(original.lower()))

This algorithm is far from optimal runtime O(n*logn), but I have chosen it because of its simplicity. For an Efficient algorithm see the comment of @corsiKa for a quite simple O(n) algorithm.

Answer 3

Inspired by MrSmith42's nice answer, I came up with a version that doesn't require sorting of the full arguments, just sorting of their Counter()s. And that sorting is triggered only if the set()s of the arguments aren't equal. That check should allow rejecting most non-anagrams very quickly, without sorting anything.

The .most_common() method of a Counter does the sorting. Counters are dictionaries that return the number of recurrences of each unique item in an iterable. The default order in which these unique items are listed is unpredictable, so sorting via .most_common() is required.

I haven't implemented case-insensitivity but that would be easy with .lower().

from collections import Counter
def is_anagram(test, original):
    if set(test) == set(original):
        return Counter(test).most_common() == Counter(original).most_common()
    return False

Update: I compared the two solutions so far (mine and MrSmith42's) for speed. The use of Counter is slower than I thought, slower than sorting the whole list. Also, I realized that in addition to set equality, anagrams must have len equality, which is another speed pre-check to use to discard non-anagrams before sorting. So combining the best elements of MrSmith42's and my answers so far, we get

def is_anagram(test, original):
    if len(test) == len(original):
        if set(test) == set(original):
            return sorted(list(test)) == sorted(list(original))
    return False

Timing:

from string import letters
from random import choice, sample
from copy import copy

import timeit 

# Make a very long random word
long_word = ''.join(choice(letters) for _ in xrange(10**6))

# Shuffle it to make an anagram
long_anagram = ''.join(sample(long_word, len(long_word)))

# A near anagram of the same length but with different character sets
wrong_chars = copy(long_anagram[:-1]) + '!'

# A near anagram but with a different length
wrong_len = copy(long_anagram) + 'a'

# the function works
print is_anagram(long_word, long_anagram)
print is_anagram(long_word, wrong_chars)
print is_anagram(long_word, wrong_len)

# when string are anagrams (or near anagrams, unchecked here) sorting is required and takes the longest
%timeit is_anagram(long_word, long_anagram)

# faster rejection of obviously wrong answers
%timeit is_anagram(long_word, wrong_chars)
%timeit is_anagram(long_word, wrong_len)

---

True
False
False
1 loops, best of 3: 486 ms per loop
10 loops, best of 3: 40 ms per loop
The slowest run took 8.11 times longer than the fastest. This could mean that an intermediate result is being cached 
1000000 loops, best of 3: 264 ns per loop

Answer 4

First check if they are the same length, if not then we can return false immediately.

Next make a list which will store the frequency for each character in the first string. ord() converts a char to its ascii value.

Then we go through the second string, and subtract 1 from each corresponding frequency, and if we go below 0, we know that a character is not in the original string (enough times). Since they are the same length, we dont' have to check the frequency list for left-over characters.

def isAnagram(original, test):
    if len(original) == len(test):
        count = [0] * ord('z') #characters up to 'z' in ascii, increase if needed
        for c in original:
            count[ord(c)] += 1
        for c in test:
            if count[ord(c)] == 0:
                return False
            else:
                count[ord(c)] -= 1
        return True
    return False

original = raw_input()
test = raw_input()

print "%s and %s are %s" % (original, test, "anagrams" if (isAnagram(original, test)) else "not anagrams")

Answer 5

def isAnagram(str1,str2):
    str1 = str1.lower()
    str2 = str2.lower()
    str1 = sorted(str1)
    str2 = sorted(str2)
    return str1 == str2

This is the simplest I can think of. Though, I am not a developer, but, just a systems engineer who likes to code

Answer 6

Its also easier to compare hashtables of each of the strings. For example,

def string2dict(st):
  d = {}
  for ch in st:
    d [ch] = d.get(ch,0) + 1
  return d

assert string2dict('aba') == string2dict('aab')