One Edit Distance

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

Example Given s = "aDb", t = "adb" return true

Note: Remember to convert size to int when doing calculation.

Solution: Single Traversal

We just need to consider three cases:

  1. If string size difference is larger than 1, return false
  2. If string size is the same, there must be only one char difference.
  3. If string size difference is 1, then if we remove one char from the longer string, the two string should be the same.
    bool isOneEditDistance(string &s, string &t) {
        for (int i = 0; i < min(s.size(), t.size()); ++i) {
            if (s[i] != t[i]) {
                if (s.size() == t.size()) return s.substr(i + 1) == t.substr(i + 1);
                else if (s.size() < t.size()) return s.substr(i) == t.substr(i + 1);
                else return s.substr(i + 1) == t.substr(i);
            }
        }

        return abs((int)s.size() - (int)t.size()) == 1;
    }

results matching ""

    No results matching ""