Posts One Edit Distance
Post
Cancel

One Edit Distance

PROBLEM DESCRIPTION

Given two strings s and t, return true if they are both one edit distance apart, otherwise return false.

A string s is said to be one distance apart from a string t if you can:

  • Insert exactly one character into s to get t.
  • Delete exactly one character from s to get t.
  • Replace exactly one character of s with a different character to get t.

leetcode

SOLUTION

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {

    public boolean isOneEditDistance(String s, String t) {

        //get lengths of both strings
        int ns = s.length();
        int nt = t.length();

        //we will make sure that ns string is of smaller length (just for convenience later)
        if(ns > nt){
            return isOneEditDistance(t, s);
        }

        //if target string has 2 or more extra characters, we cannot create it, so return false
        if(nt - ns > 1)
            return false;

        //keep comparing for each character starting from index 0
        for(int i=0; i<ns; i++){

            //if the characters do not match at index i, then we have two possibilities:
            //Possibility 1: target and source have same length:
            //example: abxcd, abycd
            //to be valid, rest of the substring from index i+1 should match for both
            //Possibility 2: they have different length:
            //example: abcd, abxcd
            //we can make it valid by deleting character at index i in target string
            //in that case, substring from index i of source should be same as substring from index i+1 of target
            if(s.charAt(i) != t.charAt(i)){

                if(ns == nt){
                    return s.substring(i+1).equals(t.substring(i+1));
                }else{
                    return s.substring(i).equals(t.substring(i+1));
                }

            }

        }

        //if all characters match, the length should be different by at least 1 character to be valid
        //example: s="" and t="" -> result should be false
        return nt - ns == 1; //return nt != ns will also work since we've already checked that diff in length is 1

    }

}
This post is licensed under CC BY 4.0 by the author.