Erician words

For some reason I really liked this small problem from PSET5 from MITx 6.00x.

Here is the problem definition:

A word is considered erician if it contains the letters e, r, i, and c in it, in that order. For example, we would say that the following words are erician: "meritocracy", "generic", "derrick", "euphoric", "heretic", and "electric", because they each contain those four letters in the correct order. The word "rice" is not erician because the four letters appear in the wrong order.

In this problem, we want you to write a more generalized function called x_ian(x, word) that returns True if all the letters of x are contained in word in the same order as they appear in x.

This algorithm works merging the two strings together and comparing character by character to determine if "x" is contained within "word".

First of all, sorry for my bad english I'm not a native speaker but I hope you can understand this solution.

Ok, this are my basic cases:

• If "x" is empty return True. This mean that all characters from "x" are contained within "word".
• If "word" is empty return False. Considering that we still have letters in "x", if we exhaust the characters from "word" that means that we don't have more characters to look at, and that means that "word" does not contains all the characters from "x" in the same order.

Now the recursive calls:

• Compare the first characters on "x" and "word".
• If they are the same, return x_ian using "x" and "word" without the first character as parameters. This means that the first character of "x" is contained within "word", on this case we don't need to keep finding the same letter in "word", so then we remove it from "x" and compare with the next character in "word" for the next recursive call.
• If they are not the same, return x_ian using the original "x" and "word" without the first character as parameter. In this second case we have not found "x", so we need to keep it the same to compare with the rest of "word".

If you analize the recursive functions we are trying to reduce the original strings until they became empty, and when we get to that point is only a matter of knowing if we don't have more characters on "x" or in "word" to determine if word contains all characters form "x" in the same order or not.

Ok, this explanation could be a little big long, but it's a lot more easy to understand when you look at the figures. (Note: Yellow means character comparison, each line represents a recursive call)

• First test case: "x" letters are contained within "word" in the same order.

• Second test case: "x" letters are not contained within Word in the same order.

• Third test case: "x" is equal to "word".

• Fourth test case: "x" and "word" are empty strings.

NE=code Not Evaluated.

On this algorithm x_ian('','') returns True as we can see the last test case.

We can even have a better algorithm if we check for x==word at the begining.

• If "x" equals to "word" return True: I don't think that this one needs an explanation ;)

I hope that this helps you to understand a way to solve this problem!