Phone keyboard autocorrect using recursion
Using C++ but this is just pseudocode so it should not matter much
This is a screenshot of typo.txt
This is part of the words.txt file
**** This week assignment specifically requires your PSEUDOCODE (do NOT submit your code). You will develop and submit the code in ZyLabs next week **** *** While # of lines does not mean a lot for pseudocode, I expect to see 20-40 lines of pseudocode for this assignment *** We are trying to imitate how swiping keyboard works in Android phone. When you swipe a word in, it gives alternate words as suggestions, taking the nearby keys into consideration. Keyboard in my android phone looks like this: qwertyuiop a s d f g h j k l 1 zxc v b n mx] Use the file words.txt as the dictionary file - it contains all the valid words that we want to consider. Another file typo.txt gives the possible alternatives (nearby keys) for each key the user types in their cellphones. Your program should read "Swiped word" and come up with the possible alternatives of same length from the dictionary (by considering alternatives for each letter of the swiped word). For example, chair can be mis-swiped in as vhair, chaie, chsir, or even vjsot. Write the detailed pseudo-code (but NOT the actual code) in plain English, it should contain - your high level approach - how dictionary data and typo configuration data is used - recursion based strategy to find all possible matches. - efficiency steps to reduce the running time - trimming the brute force approach as best as you can. Mathematical observation: Let us say the input word has n characters, MAX # of alternative suggestions are: choices (c1) * choices (c2) * choices (C3) * choices (C4) * ... choices (cn) where choices(c) is # of choices for char c (itself & alternate choices), as per the configuration file typo.txt a q w sz b v hn xf v d se fx ew sd f drg g ft yh h gy uj b i u jko jhu i kn kj i olm imkop mn kl n bh j km o i k l p po 1 red ft sa wed z t r f g y yh ji qasr z dc y tgh u za s d x aa aaa aah aahed aahing aahs aal aalii aaliis aals aam aani aardvark aardvarks aardwolf aardwolves aargh aaron aaronic aaronical aaronite aaronitic aarrgh aarrghh aaru aas aasvogel aasvogels ab aba ababdeh ababua abac abaca abacay abacas abacate abacaxi abaci abacinate **** This week assignment specifically requires your PSEUDOCODE (do NOT submit your code). You will develop and submit the code in ZyLabs next week **** *** While # of lines does not mean a lot for pseudocode, I expect to see 20-40 lines of pseudocode for this assignment *** We are trying to imitate how swiping keyboard works in Android phone. When you swipe a word in, it gives alternate words as suggestions, taking the nearby keys into consideration. Keyboard in my android phone looks like this: qwertyuiop a s d f g h j k l 1 zxc v b n mx] Use the file words.txt as the dictionary file - it contains all the valid words that we want to consider. Another file typo.txt gives the possible alternatives (nearby keys) for each key the user types in their cellphones. Your program should read "Swiped word" and come up with the possible alternatives of same length from the dictionary (by considering alternatives for each letter of the swiped word). For example, chair can be mis-swiped in as vhair, chaie, chsir, or even vjsot. Write the detailed pseudo-code (but NOT the actual code) in plain English, it should contain - your high level approach - how dictionary data and typo configuration data is used - recursion based strategy to find all possible matches. - efficiency steps to reduce the running time - trimming the brute force approach as best as you can. Mathematical observation: Let us say the input word has n characters, MAX # of alternative suggestions are: choices (c1) * choices (c2) * choices (C3) * choices (C4) * ... choices (cn) where choices(c) is # of choices for char c (itself & alternate choices), as per the configuration file typo.txt a q w sz b v hn xf v d se fx ew sd f drg g ft yh h gy uj b i u jko jhu i kn kj i olm imkop mn kl n bh j km o i k l p po 1 red ft sa wed z t r f g y yh ji qasr z dc y tgh u za s d x aa aaa aah aahed aahing aahs aal aalii aaliis aals aam aani aardvark aardvarks aardwolf aardwolves aargh aaron aaronic aaronical aaronite aaronitic aarrgh aarrghh aaru aas aasvogel aasvogels ab aba ababdeh ababua abac abaca abacay abacas abacate abacaxi abaci abacinate
