CODEWITHSUNDEEP
c++stringalgorithm
2147483647
2147483647

Reputation: 1197

How to determine if two strings are sufficiently close?

We say that we can "hop" from the word w1 to the word w2 if they are "sufficiently close". We define w2 to be sufficiently close to w1 if one of the following holds:

  1. w2 is obtained from w1 by deleting one letter.

  2. w2 is obtained from w1 by replacing one of the letters in w1 by some letter that appears to its right in w1 and which is also to its right in alphabetical order.

I have no idea how to check if 2. is fulfilled. To check if 1. is possible this is my function:

bool check1(string w1, string w2){    
    if(w2.length - w1.length != 1){
        return false;
    }
    for(int i = 0,int j = 0;i < w2.length;i++;j++){
        if(w2[i] == w1[j]){//do  nothing
        }
        else if(i == j){
            j++;
        }
        else{
            return false;
        }
    }
    return true;
}

Given two words w1 and w2, how do we check if we can 'hop' from w1 to w2?

Upvotes: 0

Views: 1094

Answers (1)

Hew Wolff
Hew Wolff

Reputation: 1509

Your algorithm for case (1) looks fine to me.

To check case (2), you can first check whether w2 has the same length as w1 and differs by exactly one character. If it does, check whether w2's character is alphabetically greater than w1's character, and whether w2's character also appears following that position in w1 (or, equivalently, in w2).

You may also want to add case (0): w1 and w2 are the same.

Upvotes: 1

Related Questions