Leetcode 161 Solution

This article provides solution to leetcode question 161 (one-edit-distance)
Categories:
Tags:
Access this page by simply typing in "lcs 161" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/one-edit-distance

Solution

class Solution {
    bool isOneModified(string& s, string& t)
    {
        int diffCnt = 0;



        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] != t[i])
                diffCnt++;



            if (diffCnt > 1)
                return false;
        }



        return diffCnt == 1;
    }



    bool isOneAdded(string& s, string& t)
    {
        int shift = 0;



        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] != t[i + shift])
            {
                shift++;
                i--;



                if (shift > 1)
                    return false;
            }
        }



        return true;
    }



public:
    bool isOneEditDistance(string s, string t) {
        int m = s.size();
        int n = t.size();



        if (m == n)
            return isOneModified(s, t);
        if (m == n + 1)
            return isOneAdded(t, s);
        if (m + 1 == n)
            return isOneAdded(s, t);



        return false;
    }
};