An improved handheld electronic device and associated method enable spell checking in a reduced keyboard and disambiguation environment. The improved spell checking routine converts a misspelled word into a canonical version thereof and receives from a dictionary 42 proposed letter for possible acceptance by the spell checking routine. The spell checking routine advantageously maintains states of various spell check algorithms in order to ensure that no letter is accepted that would require an edit distance of more than one from the misspelled word. The improved spell checking routine advantageously reduces unnecessary processor operation by reducing the extent to which certain portions of the dictionary 42 are searched multiple times during a spell checking operation.