Basic Anagram VS more advanced one
<p>I'm currently working my way through a "List" unit and in one of the exercises we need to create an anagram (for those who don't know; <em>two words are an anagram if you can rearrange the letters from one to spell the other</em>).</p>

<p>The easier solution that comes to mind is:</p>

<pre><code>def is_anagram(a, b):
    return sorted(a) == sorted(b)

print is_anagram('god', 'dog')
</code></pre>

<p>It works, but it doesn't really satisfy me. If we were in this situation for example:</p>

<pre><code>def is_anagram(a, b):
    return sorted(a) == sorted(b)

print is_anagram('god', 'dyog') #extra letter 'd' in second argument
&gt;&gt;&gt; False
</code></pre>

<p>Return is False, although we should be able to to build the word <code>'god'</code> out of <code>'dyog'</code>. Perhaps this game/problem isn't called an anagram, but I've been trying to figure it out anyway.</p>

<p><strong>Technically my solution is to:</strong><br>
1- Iterate through every element of b.<br>
2- As I do, I check if that element exists in a.<br>
3- If all of them do; then we can create a out of b.<br>
4- Otherwise, we can't.</p>

<p>I just can't seem to get it to work. <strong>For the record, I do not know how to use <code>lambda</code></strong></p>

<p><strong>Some tests:</strong></p>

<pre><code>print is_anagram('god', 'ddog') #should return True
print is_anagram('god', '9d8s0og') #should return True
print is_anagram('god', '_@10d_o g') #should return True
</code></pre>

<p>Thanks :)</p>

<p>I think all this sorting is a red herring; the letters should be counted instead.</p>

<pre><code>def is_anagram(a, b):
    return all(a.count(c) &lt;= b.count(c) for c in set(a))
</code></pre>

<p>If you want efficiency, you can construct a dictionary that counts all the letters in <code>b</code> and decrements these counts for each letter in <code>a</code>. If any count is below 0, there are not enough instances of the character in <code>b</code> to create <code>a</code>. This is an <code>O(a + b)</code> algorithm.</p>

<pre><code>from collections import defaultdict

def is_anagram(a, b):
    b_dict = defaultdict(int)

    for char in b:
        b_dict[char] += 1

    for char in a:
        b_dict[char] -= 1
        if b_dict[char] &lt; 0:
            return False

    return True
</code></pre>

<p>Iterating over <code>b</code> is inevitable since you need to count all the letters there. This will exit as soon as a character in <code>a</code> is not found, so I don't think you can improve this algorithm much.</p>

python python-2.7 python-3.x