One Edit Distance Solutions in C++

// Source : https://oj.leetcode.com/problems/one-edit-distance/
// Author : Hao Chen
// Date   : 2014-12-03

/*
 *    Given two strings S and T, determine if they are both one edit distance apart.
 */

#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <string>
using namespace std;


/*
 * Notes: 
 *
 *   If you try to use the Dynamic Program Algorithm, just like the `Edit Distance`, 
 *   Then, you will get `Memory Limit Error` or `Time Limit Error`.
 *
 *   The Dynamic Program Algorithm which `Edit Distance` prolem used call `Wagner–Fischer Algorithm`
 *   (refer to: http://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm)
 *   Ths DP algorithm's  time complexity is O(m*n), and the space complexity is O(m*n) as well, 
 *   You can optimized the space complexity to O(2*min(m,n)), but it still have `Time Limit Error`
 *
 *   Fortunately, this problem just for the `One` edit distance, so, this is special case we can solve it by special way.
 */

bool isOneEditDistance(string s, string t) {
    int len_s = s.size();
    int len_t = t.size();
    if (len_s==0) return len_t==1;
    if (len_t==0) return len_s==1;


    switch (abs(len_s-len_t)) {
        case 0:
            {
                //if these two strings have same length.
                //it means - we cannot use `add` or `delete` edit methods, just use the `replace` method
                //So, just simply count the different char(s).
                int cnt=0;
                for (int i=0; i<len_s; i++){
                    if(s[i]!=t[i]){
                        cnt++;
                        if(cnt>1) return false;
                    }
                }
                return cnt==1;
            }

        case 1:
            {
                //if these two strings' length just have ONE difference.
                //it means - we only can use `delete` edit method to delete one char in longer string.
                //So, just remove one char in longer string, and check it whether equal to shorter string.
                string& ss = (len_s > len_t)? s : t;
                string& tt = (len_s < len_t)? s : t;
                for(int i=0; i<ss.size(); i++){
                    string tmp = ss;
                    if (ss.erase(i,1) == tt) {
                        return true;
                    }
                }
                return false;

            }

        default:
            return false;
    }

    return false;
}

int main(int argc, char** argv)
{
    string s="ab", t="acb";
    if(argc>2){
        s = argv[1];
        t = argv[2];
    }
    cout << "s = \"" << s << "\"  t = \"" << t << "\"  : " << (isOneEditDistance(s,t) ? "true" : "false") << endl;
    return 0;
}

/// Source : https://leetcode.com/problems/one-edit-distance/
/// Author : liuyubobobo
/// Time   : 2019-02-14

#include <iostream>
#include <cassert>

using namespace std;


/// Three One Pass Algorithms
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {

public:
    bool isOneEditDistance(string s, string t) {

        if(s.size() == 0) return t.size() == 1;
        if(t.size() == 0) return s.size() == 1;

        if(s.size() + 1 == t.size())
            return can_add_char(s, t);
        else if(s.size() == t.size() + 1)
            return can_delete_char(s, t);
        else if(s.size() == t.size())
            return can_replace_char(s, t);
        return false;
    }

private:
    bool can_replace_char(const string& s, const string& t){

        assert(s.size() == t.size());

        int diff = 0;
        for(int i = 0; i < s.size(); i ++)
            diff += s[i] != t[i];
        return diff == 1;
    }

    bool can_delete_char(const string& s, const string& t){
        return can_add_char(t, s);
    }

    bool can_add_char(const string&s, const string& t){

        int si = 0, ti = 0;
        while(si < s.size() && ti < t.size() && s[si] == t[ti]) si ++, ti ++;
        si --;

        int sj = s.size() - 1, tj = t.size() - 1;
        while(sj > si && tj > ti && s[sj] == t[tj]) sj --, tj --;

//        cout << "si=" << si << " sj=" << sj << " ti=" << ti << " tj=" << tj << endl;
        return si == sj;
    }
};


int main() {

    string s1 = "ab", t1 = "acb";
    cout << Solution().isOneEditDistance(s1, t1) << endl;

    string s2 = "cab", t2 = "ad";
    cout << Solution().isOneEditDistance(s2, t2) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/one-edit-distance/
/// Author : liuyubobobo
/// Time   : 2019-02-14

#include <iostream>
#include <cassert>

using namespace std;


/// One Pass Algorithms
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {

public:
    bool isOneEditDistance(string s, string t) {

        if(s.size() == 0) return t.size() == 1;
        if(t.size() == 0) return s.size() == 1;

        int si = 0, ti = 0;
        while(si < s.size() && ti < t.size() && s[si] == t[ti]) si ++, ti ++;
        si --, ti --;

        int sj = s.size() - 1, tj = t.size() - 1;
        while(sj > si && tj > ti && s[sj] == t[tj]) sj --, tj --;

        if(si + 1 == sj && ti == tj) return true;
        if(ti + 1 == tj && si == sj) return true;
        if(si + 1 == sj && ti + 1 == tj) return true;
        return false;
    }
};


int main() {

    string s1 = "ab", t1 = "acb";
    cout << Solution().isOneEditDistance(s1, t1) << endl;

    string s2 = "cab", t2 = "ad";
    cout << Solution().isOneEditDistance(s2, t2) << endl;

    return 0;
}