Created
February 13, 2012 20:30
-
-
Save leegao/1819957 to your computer and use it in GitHub Desktop.
How many anagrams are there?
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Assume the average length m of each word << the length of the list of words, which we call n | |
# The following will run in O(n*mlgm) Now assuming that we're using words from | |
# the english language, then the mlgm factor goes to around 6*C | |
# so the overall runtime should scale linearly with the size of the input length | |
def anagrams(file): | |
dict = {} | |
count = set() | |
for line in open(file): | |
sline = "".join(sorted(line)) | |
if sline in dict: | |
count.add(sline) # change to line to find how many are part of the list of anagrams | |
dict[sline] = 0 | |
return len(count) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment