One Away

1.5 One Away: There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away.

• Brainstorm:

  • Removal, insertion, and replacement all describe a single difference in character. So all we have to test for it similarity between the two words.

EXAMPLE
pale, ple -> true
pales, pale -> true
pale, bale -> true
pale, bake -> false

bool oneAway(string s1, string s2) {
    int s1Len = s1.length();
    int s2Len = s2.length();
    if (s1 == s2) return true;
    if (abs(s1Len - s2Len) > 1) return false;

    int countMatch = 0;
    int j = s2.length() - 1;

    // backwards to avoid edge cases

    if (s1Len > s2Len) {
        for (int i = s1Len - 1; i >= 0; i--) {
            // if at end, and no mistakes
            if (countMatch > 1) {
                return false;
            }
            else if (s1.at(i) != s2.at(j)) {
                countMatch++;
                j++;
            }
            j--;
        }
        return true;
    }

    j = s1.length() - 1;

    // s2 larger
    for (int i = s2Len - 1; i >= 0; i--) {
        // if at end, and no mistakes
        if (countMatch > 1) {
            return false;
        }
        else if (s2.at(i) != s1.at(j)) {
            countMatch++;
            j++;
        }
        j--;
    }
    return true;


}

int main() {
    cout << boolalpha << oneAway("danie", "daniel") << endl;
    cout << boolalpha << oneAway("daniel", "danie") << endl;
    cout << boolalpha << oneAway("pales", "pale") << endl;
    cout << boolalpha << oneAway("pale", "bale") << endl;
    cout << boolalpha << oneAway("pale", "bake") << endl;
    cout << boolalpha << oneAway("bale", "pake") << endl;
    cout << boolalpha << oneAway("clound", "clounnd") << endl;
}