An exercise in the Python version of How to Think Like a Computer Scientist at first struck me as dumb, then in a flash I had the answer. Come up with a function that would determine if one word was an anagram of the other.
Immediately, I saw what would be an easy mistake: going letter by letter through the first word looking to see if the letter appeared in the second word. It would be easy to write a routine that would see P E E L E D as an anagram of P E D D L E, since theyre both made up of P, E, L and D.
My solution would turn each word into lists, search for a letter in wordList1 into wordList2, and when it was found, replace the letter with a nonalphabetic character, *. If the loops reach the end, the words are anagrams.
Here:
I was sufficiently proud of myself and decided to call it a night. As Im brushing my teeth, I realize just how stupid I was. If the two lists were sorted, they would be equal if the words were anagrams.
Like this:
Sure enough, No. 2 works like a charm. I clung to the hope that checking the equality of two lists is so inefficient that somehow my original routine was faster. Not a chance. I mocked up some brute force timing (essentially wrapping each isAnagram statement with a 100,000 iteration for loop) and the second version takes half the time of the first.
So theres an important lesson here: Never be too impressed with your coding because theres almost always a faster way to get something done.
mt
Immediately, I saw what would be an easy mistake: going letter by letter through the first word looking to see if the letter appeared in the second word. It would be easy to write a routine that would see P E E L E D as an anagram of P E D D L E, since theyre both made up of P, E, L and D.
My solution would turn each word into lists, search for a letter in wordList1 into wordList2, and when it was found, replace the letter with a nonalphabetic character, *. If the loops reach the end, the words are anagrams.
Here:
Code:
def isAnagram(word1,word2):
wordList1, wordList2 = list(word1), list(word2)
if len(wordList1) <> len(wordList2):
return False
where = -1
for ch1 in wordList1:
for counter in range (0, len(wordList2)):
if ch1 == wordList2[counter]:
where = counter
break
if where == -1:
return False
else:
wordList2[counter] = '*'
where = -1
print str(wordList2) # this print statement isn't needed
# but I think it's cool to watch the iterations
return True
firstWord, secondWord = raw_input('Please enter first word: '), raw_input('Please enter second word: ')
print isAnagram(firstWord,secondWord)I was sufficiently proud of myself and decided to call it a night. As Im brushing my teeth, I realize just how stupid I was. If the two lists were sorted, they would be equal if the words were anagrams.
Like this:
Code:
def isAnagram(word1,word2):
x,y = list(word1), list(word2)
x.sort(), y.sort()
# print str(x), str(y)
return (x == y)
firstWord, secondWord = raw_input('Please enter first word: '), raw_input('Please enter second word: ')
print isAnagram(firstWord,secondWord)Sure enough, No. 2 works like a charm. I clung to the hope that checking the equality of two lists is so inefficient that somehow my original routine was faster. Not a chance. I mocked up some brute force timing (essentially wrapping each isAnagram statement with a 100,000 iteration for loop) and the second version takes half the time of the first.
So theres an important lesson here: Never be too impressed with your coding because theres almost always a faster way to get something done.
mt
I hadn't thought of sorting the strings to compare for anagrams until I read your post.