Most modern text processing systems have a built-in spelling checker, which checks to make sure words are spelled correctly and offers suggested corrections when words are misspelled. Suppose you have a dictionary, D, of n English words and would like to build such a spelling checker for two common spelling mistakes: transpositions, where two consecutive letters are swapped, and substitutions, where a single letter is replaced with a different letter. Describe a scheme to process the dictionary D in expected O(n) time and then process any m-letter word, w, to see if w is spelled correctly, and, if not, to collect all the suggested correct English words that differ from w in a single transposition or substitution. The processing of any such w should take O(m + s) time, where s is the total length of all the suggested alternatives to w.