logo CodeStepByStep logo


Language/Type: C++ recursion backtracking Lexicon
Related Links:
Author: Marty Stepp (on 2016/10/17)

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.

Type your C++ solution code here:

This is a function problem. Write a C++ function as described. Do not write a complete program; just the function(s) above.

You must log in before you can solve this problem.

Log In

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.

© Marty Stepp, all rights reserved.