161. (Locked)One Edit Distance

Difficulty: Medium

Frequency: N/A

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

 


My solution:
Data structure:
string
Steps:
1. compare the size of S and T.
1.1 If s.size() == t.size(), there should be only one replace operation
1.2 If s.size() – t.size() == 1, or t.size() – s.size() == 1, one insertion or deletion
1.3. otherwise, return false.
Complexity:
Runtime: O(n)
Space: O(1)
Test cases:
Corner cases:
“” “”
“a” “”
“a” “b”
Code:

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        if (s.size() < t.size()) s.swap(t);
        if (s.size() - t.size() > 1)
            return false;
        int distance = 0;
        for (int i = 0, j = 0; i < s.size(); i++, j++) {
            if (s[i] == t[j]) continue;
            else if (distance > 1) return false;
            else {
                distance++;
                i = s.size() > t.size() ? i++: i;
            }
        }
        return true;
    }
}

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
1. By calling the function itself, you can swap the input parameters.
Advertisements

One thought on “161. (Locked)One Edit Distance

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s