Find whether two words are anagrams (cafe / face)
- Go to first word in hash table, add 1 in hash table then see whether all letters of 2nd word also in hash table, if it reaches end of 2nd word it means it is a anagram. Issue: 2 same letters in the word
- Increment values in the hash table instead of storing 1 for the first word & then for the 2nd word, decrement values, if all values 0 at the end of 2nd word - it means anagram Complexity = 3n (parse 1st word, parse 2nd word, parse the array)
Create sets of anagrams from a word list (cafe, face, fdga, dgfa - you you will have 2 lists => cafe/face & fdga/dgfa)
- Go to first word, see if any lists, if a list take a word from that list & run the above function for that two words, if return true then add to that list, if false do this for all the lists, create a new list with that word is still that word not in any list Complexity = l * 3n * x (l-no of words, x-no of unique lists)
- sort each word & sort list & then group
- aefc, aefc, adfg, adfg
- Complexity =>
- sorting = nlogn
- sorting each word = nlogn * size of each word
- sorting list = l*log l * total no of words
- total complexity = sorting each word + sorting list + grouping
No comments:
Post a Comment