logo CodeStepByStep logo


Language/Type: C++ recursion backtracking Lexicon
Related Links:

Write a recursive function named listTwiddles that accepts a string str and a reference to an English language Lexicon and uses exhaustive search and backtracking to print out all those English words that are str's twiddles. Two English words are considered twiddles if the letters at each position are either the same, neighboring letters, or next-to-neighboring letters. For instance, "sparks" and "snarls" are twiddles. Their second and second-to-last characters are different, but 'p' is two past 'n' in the alphabet, and 'k' comes just before 'l'. A more dramatic example: "craggy" and "eschew" are also twiddles. They have no letters in common, but craggy's 'c', 'r', 'a', 'g', 'g', and 'y' are -2, -1, -2, -1, 2, and 2 away from the 'e', 's', 'c', 'h', 'e', and 'w' in "eschew". And just to be clear, 'a' and 'z' are not next to each other in the alphabet; there's no wrapping around at all. (Note: any word is considered to be a twiddle of itself, so it's okay to print str itself.)

Constraints: Do not declare any global variables. You can use any data structures you like, and your code can contain loops, but the overall algorithm must be recursive and must use backtracking. You are allowed to define other "helper" functions if you like; they are subject to these same constraints. Do not modify the state of the Lexicon passed in.

Function: Write a C++ function as described, not a complete program.

You must log in before you can solve this problem.

Log In

Need help?

Stuck on an exercise? Contact your TA or instructor.

If something seems wrong with our site, please

Is there a problem? Contact us.