Simple Java Solution - O(n) Time & O(1) Space


  • 0
    C

    Basic idea is as follows:
    Using 2 pointers to go through each string and compare if the characters are the same. When there is an disagreement, jump out of inner loop and increase one of the pointers by 1. (if s.length() < t.length(), increase the pointer of t, otherwise increase that of s)

    Return true if we reach the end of either of them, otherwise check if the disagreement occurs for the first time. If so make increment indicated above, otherwise return false. (since in this situation, the distance apart is more than 1)

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

Log in to reply
 

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