Home
Map
Anagram MethodFind anagrams within a word list. Use sorted strings and a dictionary.
Python
This page was last reviewed on May 21, 2023.
Anagrams. Finding anagrams, words made up of letters of other words, is a classic computer programming puzzle. Solutions can be simple, slow, complex or fast.
A simple approach. One way to find one-word anagrams is to sort each word's chars in a word list. Then, in a dictionary, use those sorted strings as keys. Values are the possible words.
Our implementation. Consider this program. It has three methods. In build_dict we load in a file and parse it—we strip lines, sort their characters, and then add them to a dictionary.
String strip
Dictionary
Note Sorted_line alphabetizes the characters in a string. It uses a list comprehension to get a list, then sorts it and joins it.
sort
Note 2 The anagram() method returns a list of anagrams for a word. It sorts again and splits the result string from the dictionary.
def build_dict(path): # Load in word file and sort each line. alpha = {} f = open(path, "r") for line in f.readlines(): line = line.strip() key = sorted_line(line) # Add each line to a dictionary based on its sorted key. if key in alpha: v = alpha.get(key) + "," + line alpha[key] = v else: alpha[key] = line return alpha def sorted_line(line): # Sort the chars in this line and return a string. chars = [c for c in line] chars.sort() return "".join(chars) def anagram(alpha, line): # Return a list of anagrams from the dictionary. # ... Use a sorted string as the key. key = sorted_line(line) values = alpha.get(key, "NONE") return values.split(",") # Load our dictionary and use it. alpha = build_dict(r"C:\enable1.txt") results = anagram(alpha, "spot") print("Anagrams for [spot]") print(results)
Anagrams for [spot] ['opts', 'post', 'pots', 'spot', 'stop', 'tops']
Design notes. The values in the dictionary are stored as strings. Each string is separated by commas. This approach is not ideal but may be simpler (and faster) to use.
Tip For top performance, a directed acyclic graph is used to find anagrams. Matches can be found by a simple tree traversal.
Most programming tasks involve no anagrams. In fact they often involve no algorithms at all. But practicing with these concepts can lead to new ideas, new inventions.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
This page was last updated on May 21, 2023 (simplify).
Home
Changes
© 2007-2023 Sam Allen.