CSC148H5 Lecture Notes - Lecture 9: Anagram, Anagrams, Linear Search
Document Summary
Anagrams our definition: two words are anagrams if the letters of one dictionary word can be rearranged to be the letters of the other dictionary word. Bill, lib no, not the same letters. Yes, a word is the anagram of itself. N! (factorial) for each permutation, we need to linear search through a list of size m, so the total runtime is at least n! x m. E. g, the word is mississauga and the word list has 20,000 words. # of steps 11! x 20,000 = 39,916,800 x 20,000 = 798,336,000,000 this is going to take a long, long time to finish, even on a computer. Approach #2: signature thinking about the efficiency of approach #1: The number of permutations is huge when the length of the word is a bit large, and the vast majority of those permutations are not even in the dictionary word list. Going through them is a waste of time.
