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

**Understand the problem:**

Note that the problem asks for EXACTLY one edit distance. There are several cases to consider:

-- If the len1 - len2 > 1, return false;

-- We compare each character of the two strings. if not equal.

-- If len1 > len2, we move i++, which means delete one character from string1, e.g. abc, ac

-- If len1 < len2, we move j++, which add one character for string1 (or delete one from string 2).

-- If len1 == len2, i++, j++

**Code (Java):**

public class Solution { public boolean isOneEditDistance(String s, String t) { if ((s == null || s.length() == 0) && (t == null || t.length() == 0)) { return false; } if (s == null || s.length() == 0) { return t.length() == 1; } if (t == null || t.length() == 0) { return s.length() == 1; } if (Math.abs(s.length() - t.length()) > 1) { return false; } int count = 0; int i = 0; int j = 0; while (i < s.length() && j < t.length()) { if (s.charAt(i) != t.charAt(j)) { count++; if (count > 1) { return false; } if (s.length() > t.length()) { i++; } else if (s.length() < t.length()) { j++; } else { i++; j++; } } else { i++; j++; } } if (i < s.length() || j < t.length()) { count++; } return count == 1; } }

**Summary:**

The problem itself is not hard, but very tricky to get the OJ passed. Some tricks need to be very very careful:

1. If the length of the two words diff more than 1, directly return false;

2. At the end, we need to check if i < s.length() OR j < t.length(). That is because the problem asks for EXACTLY ONE edit distance. e.g. s = abc, t = ab, in this case. the count = 0. So we need to accumulate the count by 1 in that case. If the problem asks for edit distance which is LESS or EQUAL to 1, then we don't need to check that step.

## No comments:

## Post a Comment