Preparing for repeated chars in strings - algorithm

Question

Given three strings a, b and c. Trying to check whether c is an interspersed version of a and b, recursively.

So an example would be.

a = dolphin
b = whale
c = dolwhphialne

You can see that the chars in the c string are in the same order as they would be in their original strings, just shuffled up a little bit.

The algorithm I'm working on is.

Algorithm: stringOrderedCheck(a,b,c)
    n:= length of a
    m:= length of b
    nm:= length of a and b
    if (nm > 0) then
        if(first letter of a equals first letter of c) then
            return stringOrderedCheck(a without first letter,b, c without first letter)
        else if(first letter of b equals first letter of c) then
            return stringOrderedCheck(a,b without first letter, c without first letter)
    else 
        return false;

But the problem that I am getting is this for example:

a = yyyyb
b = yyyx
c = yyyyxyyyb

How do I prepare the function to realise that it needs to take the first letter from a which is y then take the next 4 from b which is yyyx.

Duplicate values are causing me a major issue.

I need to do something when both chars in a and b equal the char in c

length of a and b What are you calculating here? The sum? The minimum? — user824425
– user824425, Commented Nov 10, 2015 at 22:37

R Nar · Accepted Answer · 2015-11-10 22:40:37Z

1

I believe that the main problem here is that, at this point, your path can split into two separate recursive calls, ie the tree divides rather than just going deeper. the problem is that because of your else if, the second path is only ever even considered if the first path is not, ie, it never considers both. you can then prepare for this:

#your original code
if(first letter of a equals first letter of c) then
        return stringOrderedCheck(a without first letter,b, c without first letter)
else if(first letter of b equals first letter of c) then
        return stringOrderedCheck(a,b without first letter, c without first letter)

you can change this into:

if(first letter of a equals first letter of c) then
    if(first letter of b equals first letter of c) then
        return stringOrderedCheck(a without first letter,b, c without first letter) OR stringOrderedCheck(a,b without first letter, c without first letter)
    else
        return stringOrderedCheck(a without first letter,b, c without first letter)
else if(first letter of b equals first letter of c) then
        return stringOrderedCheck(a,b without first letter, c without first letter)

so that it checks for both regardless of the condition of the first one.

you can also change this by saving your bool as a variable before the if checks then asserting a general or:

valid:= false
if(first letter of a equals first letter of c) then
        valid = valid or stringOrderedCheck(a without first letter,b, c without first letter)
if(first letter of b equals first letter of c) then #take out the else so it will always check
        valid = valid or stringOrderedCheck(a,b without first letter, c without first letter)
return valid

this last solution shows a pretty important note: make sure you have an else after your if/else if statement that returns false (if you dont use the last solution) to account for if the first letter of c is straight up just not valid (ie not the first letter of a or b)

answered Nov 10, 2015 at 22:40

R Nar

5,5231 gold badge20 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

user824425 Over a year ago

Minor detail to note: this algorithm works best when the or-operator is short-circuiting. That is, if the expression on the left hand side evaluates to true, the expression on the right hand side is never evaluated. This may save quite a few unnecessary searches.

user5530090 Over a year ago

Thank you for the answer, I will attempt to implement it.

R Nar Over a year ago

@Rhymoid good point, because im used to python, I had assumed that this was the case but I forgot that this was just a general pseudocode :P

user5530090 Over a year ago

for some reason I'm getting an error when one of the strings is empty @Rhymoid

R Nar Over a year ago

its kind of hard to assess how to fix that with pseudo code but assuming you are doing something like a[0] to grab the first letter, if a is an empty string, that would cause an out of index error. i suggest doing an initial check if a/b are empty and working with that accordingly

|

Collectives™ on Stack Overflow

Preparing for repeated chars in strings - algorithm

1 Answer 1

9 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Related