[LintCode][Facebook] One Edit Distance

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

One edit distance means doing one of these operation:

• insert one character in any position of S
• delete one character in S
• change any one character in S to other character

Example:

Input: s = "aDb", t = "adb"
Output: true
Explanation: change D to d in s

Input: s = "ab", t = "ab"
Output: false
Explanation: s and t are same.

Approach: We can use the standard Edit Distance algorithm and check if the result is 1 that will definitely work. Let's try some other approach too. We need to check the following:

1. If difference between length of s and t is more than 1 than we can safely return false.
2. If above difference is 1 then we just need to check if removal of one character in bigger string makes both the strings same.
3. If length of s and t are same than we just need to ensure that the number of places the characters are different in s and t is 1.

That's all!

Implementation in C#:

        public bool IsOneEditDistance(string s, string t)

{

if (s == t)

{

return false;

}

if (Math.Abs(s.Length - t.Length) > 1)

{

return false;

}

if (s.Length > t.Length)

{

return this.CanOneDeleteWork(s, t);

}

if (t.Length > s.Length)

{

return this.CanOneDeleteWork(t, s);

}

int diferences = 0;

for (int i = 0; i < s.Length; ++i)

{

if (s[i] != t[i])

{

++diferences;

if (diferences > 1)

{

return false;

}

}

}

return true;

}

private bool CanOneDeleteWork(string bigStr, string smallStr)

{

int length = smallStr.Length;

for (int i = 0; i < length; ++i)

{

if (bigStr[i] != smallStr[i])

{

return bigStr.Substring(i + 1).Equals(

                        smallStr.Substring(i));

}

}

return true;

}

Complexity: O(m * n)