Java/Python two pointer solution


  • 5

    If s and t are one distance away then no matter it is insert or delete or replace the count of common characters must be max(m, n) - 1, where m is the length of s and n is the length of t. It is easy to see that the reverse is also true.

    Assume the length of common prefix (from left to right) is i and the length of common suffix after i (from right to left) is j, the answer is then max(m, n) - 1 == i + j

    Example 1 (1 replace)

    s = "abcdefg", m = 7
    t = "abcxefg", n = 7 
    i = 3, j = 3
    max(m, n) - 1 == i + j is true
    

    Example 2 (0 edit)

    s = "abcdefg", m = 7
    t = "abcdefg", n = 7 
    i = 7, j = 0
    max(m, n) - 1 == i + j is false
    

    Example 3 (1 insert)

    s = "abcdefg", m = 7
    t = "abcefg", n = 6 
    i = 3, j = 3
    max(m, n) - 1 == i + j is true
    

    Example 4 (1 delete 1 insert)

    s = "abcdefg", m = 7
    t = "abcefgh", n = 7 
    i = 3, j = 0
    max(m, n) - 1 == i + j is false
    

    The method is O(m+n) since any character is visited at most once.

    Java

    public boolean isOneEditDistance(String s, String t) {
        int m = s.length(), n = t.length();
        if (Math.abs(m - n) > 1) return false;
        int k = Math.min(m, n);
        int i = 0, j = 0;
        while (i < k && s.charAt(i) == t.charAt(i)) ++i;
        while (j < k - i && s.charAt(m - 1 - j) == t.charAt(n - 1 - j)) ++j;
        return m + n - k - 1 == i + j;
    }
    // Runtime : 2ms
    

    Python

    def isOneEditDistance(self, s, t):
        n, m = len(s), len(t)
        if abs(n - m) > 1:
            return False
        k = min(n, m)
        i = j = 0
        while i < k and s[i] == t[i]:
            i += 1
        while j < k - i and s[~j] == t[~j]:
            j += 1
        return max(n, m) - (i + j) == 1
    
    
    # 129 / 129 test cases passed.
    # Status: Accepted
    # Runtime: 40 ms
    # 96.05%

  • 0

    Could use ~ again :-)
    s[~j] == t[~j]


  • 0

    Played a bit more with it, actually using the complement for j and determining the small and large length right away.

    def isOneEditDistance(self, s, t):
        n, N = sorted((len(s), len(t)))
        if N - n > 1:
            return False
        i, j = 0, -1
        while i < n and s[i] == t[i]:
            i += 1
        while ~j < n - i and s[j] == t[j]:
            j -= 1
        return i - j == N

  • 0

    Complement can make the code clean but it is kind of harder for whoever read the code. Do you think it is a good idea to write this on a whiteboard coding interview? The interviewer could either be impressed or be irritated, ~~~ or both ~~~ :-)


  • 0

    I don't know, I'm not going to interviews :-). But I don't think of it as complement and negative indexes. I simply think of it as 0-based backwards-indexing. I think it makes it easier, not harder. Yes, the first time someone sees it, it might be confusing, but then you just think it through, remember it, and are better off. Everybody should know it, in my opinion :-). And I'd most likely indeed use foo[~i] instead of foo[n-1 - i] or even foo[len(foo)-1 - i] when coding with someone, though I'd probably ask whether they're familiar with it, and briefly explain if not.


  • 0

    That said, I wouldn't use while ~j < n - i like I did there, I just happened to end up with that when I fiddled with the code. I don't see a meaning in it and it's confusing me as well :-P


  • 0

    I do like the way you think ~i.


  • 0
    S

    Java code.
    The complexity is O(N) I think because we are traversing i from 0 to k from left and j from right end to k - i


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.