listing the twiddles of a string

  backtracking, c++, vector

Two strings s1 and s2 are Twiddles if they have the same length and each character in the same position differs by at most 2. For instance, "eschew" and "craggy" are Twiddles as the differences between consecutive characters are respectively -2, -1, -2, -1, 2, 2. I’m trying to write a function listTwiddles that takes in a string str1 and a vector of strings as parameters and uses backtracking to print all strings in the vector of strings that are str1’s Twiddles. However, I’m not sure how to use backtracking; I can think of a relatively easy iterative method, shown below, though.

As for the backtracking approach, I was thinking of defining a helper function and removing one character from str and calling the helper function again, but I’m not sure how this will help.

int abs(int a) { return a < 0 ? -a : a; }

bool isTwiddle(string s1, string s2) {
    if (s1.size() != s2.size()) return false;
    for (int i = 0; i < s1.size(); ++i) {
        if (!(abs(s1[i] - s2[i]) <= 2)) return false;
    }
    return true;
}

void listTwiddles(string str, vector<string> lexicon) {
    for (int i = 0; i < lexicon.size(); ++i) {
        if (isTwiddle(lexicon[i], str)) cout << lexicon[i] << endl;
    }
}

Source: Windows Questions C++

LEAVE A COMMENT