Code works but I don't understand if it is correct

Claudius7 (42)
Hi, I have made a code to check if edit distance between two strings is one, it seems that it works when I run it, but I honestly I don't understand why, for two reasons that I will explain later.

The idea of my code is the following: after I check if the two strings have same number of characters, I consider the only relevant case, i.e. they differ by only one character. Then, I take the shortest string, and I check character by character. If I find that at some point, str1[i] is different than str2[i], I increase the index of the second string str2 by 1, and I go ahead checking now str[i] with str2[i+1]. If the remaining characters are all equal, then the two strings are one character away, otherwise they are not.

Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
    #include <iostream>
    #include <algorithm>
    #include <string>

    using namespace std;

    bool one_away(const string& str1, const string& str2)
     {
      int lgth1 = str1.length();
      int lgth2 = str2.length();      // lengths of the two strings

      if (abs(lgth1 - lgth2) > 1) // If the strings differ by more than one char
        return false;            // they cannot be one char away from the other

        if (abs(lgth1 - lgth2) == 0) //if equal nr of chars, check they're equal
        {
            int tmp = 0;
            for (int i=0; i < lgth1; ++i)
            {
                if (str1[i] != str2[i])
                    ++tmp;
            }
            if (tmp == 0 || tmp == 1)
                return true;
                return false;
        }
        if (abs(lgth1 - lgth2) == 1) // General case  
        {                                   
            for (int i=0; i < lgth1; ++i)
            {
                if (str1[i] != str2[i])     
                {                           
                    for (int j=i+1; j < lgth2; ++j) 
                    {
                        if (str1[i] != str2[j])
                            return false;
                    }
                    return true;
                }
                return true;
            }
        }
    }

    int main()
    {
        string s1 = "pasle";
        string s2 = "pale";
        cout << "are the string admissible? 1=yes, 0= no " << endl;
        cout << one_away(s1, s2) << endl;
        return 0;
    }


Now, all seems okay but I realised two problems: 1) nowhere in the code I specified that str1 must be the one with the least number of charaters, and yet the code seems to work even in this case. Also, I was wondering if the second for loop inside the first is correct: suppose that the program verifies that str1[i] == str2[j] the first time (i.e., j=i+1). What happens next? The next step is to restart with the loop in i and so it verifies if str1[i+1] is equal to str2[j+1], or does it first complete the loop on j and then moves back to increase i to i=1?

Edit: apparently, the code does not work, contrary to what I claimed in the title. So, my question is: what is a correct code for this problem?
Last edited on
keskiverto (10425)
"Correct" can be many things. These tools look interesting:

http://www.cplusplus.com/reference/string/string/swap-free/
http://www.cplusplus.com/reference/algorithm/mismatch/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
bool one_away( std::string str1, std::string str2 )
{
  if ( str2.length() < str1.length() ) std::swap( str1, str2 );

  const auto lgth1 = str1.length();
  const auto lgth2 = str2.length();
  if ( lgth1 == lgth2 ) {
    // something
  }
  else if ( lght1 + 1 == lght2 ) {
    // something
  }
  else {
    return false
  }
}
Topic archived. No new replies allowed.