Write a recursive function weave that is given two strings s1 and s2 and uses backtracking to attempt to form a third word s3 consisting of all of the letters from s1 and s2 merged ("woven") together.
The relative order of the letters must be preserved, meaning that s1 and s2 must both be subsequences of s3.
For example, if s1 is "cook" and s2 is "red", a result s3 of "crooked" would be suitable.
It contains the letters of s1: "crooked" and the letters of s2: "crooked".
Notice that s1 and s2 are subsequences of s3, but not necessarily substrings; this means that the letters of s1 or s2 do not need to occur consecutively in s3, but they must all occur in s3 in the same relative order in s3 that they did in s1 and s2.
For example, "me" and "sat" cannot merge to form "teams" because the letters are not in the same relative order in the result.
Note that a letter in s3 could correspond to a letter from both s1 and s2.
For example, if s1 is "arts" and s2 is "rests", an s3 of "arrests" would be suitable because it contains all of s1: "arrests" and all of s2: "arrests".
Notice that the "ts" at the end of "arrests" corresponds to the "ts" of both "arts" and "rests".
You will be passed three parameters: two strings s1 and s2 to try to weave, and a reference to a Lexicon of dictionary words.
If the function finds a suitable merging of s1 and s2, it prints the resulting word and searches no further.
If no suitable merge is found, the function prints nothing.
The function should also return a bool value of true if a merged word was found and printed, or false if not.
Use the Lexicon passed to ensure that any result you weave together is a valid word that is found in the dictionary.
You must also use it to optimize your exploration by avoiding paths that cannot possibly lead to a valid solution.
(Note: Do not perform a for-each loop over every word in the lexicon.
Such solutions are on the wrong track and will not receive high scores.)
The following table lists some example calls to your function, the expected return values, and possible output to appear on the console, given a Lexicon called dict:
Lexicon dict; ...
| Call |
Returns |
Possible Output |
weave("cook", "red", dict) |
true |
crooked |
weave("arts", "rests", dict) |
true |
arrests |
weave("bets", "east", dict) |
true |
beasts |
weave("house", "dog", dict) |
true |
doghouse |
weave("huge", "nerd", dict) |
true |
hungered |
weave("dog", "", dict) |
true |
dog |
weave("", "kitten", dict) |
true |
kitten |
weave("enter", "exit", dict) |
false |
|
weave("met", "tall", dict) |
false |
|
weave("dog", "use", dict) |
false |
|
weave("", "", dict) |
false |
|
.
If there are multiple valid words that can be made by weaving s1 and s2, you may print any of them.
Regardless of which word you print, your code must stop after finding a single solution; do not find/print all possible solutions.
Efficiency: While your code is not required to have any particular Big-Oh, you should avoid code that is extremely inefficient or repeatedly re-explores the same path multiple times.
Pass data structures by reference to avoid making copies.
Constraints: Obey the following restrictions.
A solution that disobeys them can get partial credit.
- Do not declare any global variables.
- Your code can contain loops if needed to solve the problem, but your overall algorithm must be recursive and must use backtracking techniques to generate the results.
- You are allowed to define other "helper" functions if you like; they are subject to these same constraints.
