Combines an efficient trie datastructure to both check validity of, and find near matches for, inputted text while finding the best alternatives for mistakes through Markov chain word sequence probabilities and keyboard key placement.
O(n) lookup for checking word validity, where n is the length of the word.
O(1) lookup for Markov chain-based word probabilities