161. One Edit Distance
Problem Description
The problem provides two strings, s
and t
, and asks us to determine if they are one edit distance apart. Being "one edit distance apart" means that there is exactly one simple edit that can transform one string into the other. This edit can be one of the following types:
- Inserting exactly one character into
s
to gett
. - Deleting exactly one character from
s
to gett
. - Replacing exactly one character in
s
with a different character to gett
.
To solve this problem, we need to carefully compare the two strings and verify if they differ by exactly one of the aforementioned operations or, in contrast, they are either identical or differ by more than one operation.
Intuition
The solution exploits the fact that if two strings are one edit distance apart, their lengths must differ by at most one. If the lengths differ by more than one, more than one edit is required, which violates the problem constraints. Therefore, the solution begins by comparing the lengths of s
and t
:
-
If
s
is shorter thant
, swap them to ensure that we only have one case to handle for insertions or deletions (the case wheres
is longer than or equal tot
). -
If the difference in lengths is greater than one, return
False
immediately. -
Iterate over the shorter string and compare the characters at each index with the corresponding characters in the longer string.
-
The moment a mismatch is encountered, there are two scenarios to consider based on the length of the strings:
-
If
s
andt
are of the same length, the only possible edit is to replace the mismatching character ins
with the character fromt
. Check if the substrings ofs
andt
after the mismatch indices are identical. -
If
s
is longer thant
by one, the only possible edit is a deletion. Check if the substring ofs
after the mismatch index plus one is identical to the substring oft
after the index of the mismatch.
-
-
If no mismatch is found and the loop completes, one last check is needed: if
s
is longer thant
by one character, then the last character ofs
could be the extra character, satisfying the condition for being one edit distance apart.
In conclusion, this solution systematically eliminates scenarios that would require more than one edit and carefully checks for the one allowed edit between the given strings.
Learn more about Two Pointers patterns.
Solution Approach
The implementation of the solution provided uses a straightforward approach that does not rely on any additional data structures or complex patterns. Let's take a closer look at the algorithm:
-
Check Lengths and Swap: The function begins by making sure that
s
is the longer string. If it's not, it calls itself with the strings reversed.1if len(s) < len(t): 2 return self.isOneEditDistance(t, s)
This optimizes the code by allowing us to only think about two scenarios (instead of three): replacing a character or deleting a character from
s
. -
Check Length Difference: If the length of
s
is more than one character longer thant
, they cannot be one edit apart, so the function returnsFalse
.1if m - n > 1: 2 return False
-
Iterate and Compare Characters: The next step involves iterating over the shorter string
t
and checking character by character to find any differences.1for i, c in enumerate(t): 2 if c != s[i]:
As soon as a difference is found, the function moves to the next step.
-
Check Possible One Edit Scenarios: Upon encountering a mismatch, there are now two cases to consider:
-
For strings of the same length (
m == n
), a replacement might be the one edit. The function checks if the substrings after the different characters are the same.1return s[i + 1 :] == t[i + 1 :]
-
If
s
is longer by one character (m == n + 1
), it indicates a possible deletion. The code checks if the substring ofs
beyond the next index is the same as the substring oft
from the current index.1return s[i + 1 :] == t[i:]
-
-
Final Check for Deletion at the End: If the
for
loop finishes without finding any mismatches, the function finally checks ifs
is exactly one character longer thant
, which would imply the possibility of the one edit being a deletion at the end.1return m == n + 1
Throughout its process, this approach relies purely on the properties of strings and their indices. It uses string slicing to compare substrings and eliminate the need for additional operations. This makes for an efficient approach both in terms of space, not requiring any additional storage, and in terms of time, as it can short-circuit and exit as soon as it finds the strings are not one edit distance apart.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example. Consider two strings s = "cat"
and t = "cut"
. We want to determine whether they are one edit distance apart using the above solution approach.
-
Check Lengths and Swap: Since the length of
s
is equal tot
, no swapping occurs.1if len(s) < len(t): 2 return self.isOneEditDistance(t, s)
-
Check Length Difference: The lengths of
s
andt
are the same, so this condition is not triggered.1if m - n > 1: 2 return False
-
Iterate and Compare Characters: We iterate over each character in
t
and compare it with the corresponding character ins
.1for i, c in enumerate(t): 2 if c != s[i]:
The loop encounters a mismatch at index 1:
'a'
ins
is different from'u'
int
. -
Check Possible One Edit Scenarios: Since
s
andt
are of the same length, we check if replacing the second character ins
with the corresponding character int
would make the strings equal.1 return s[i + 1 :] == t[i + 1 :]
This returns
True
ass[2:]
('t') is identical tot[2:]
('t'), indicating that replacing 'a' with 'u' ins
results int
.
So, s
and t
are indeed one edit distance apart as we only need to replace one character ('a' with 'u') to transform s
into t
.
Solution Implementation
1class Solution:
2 def isOneEditDistance(self, s: str, t: str) -> bool:
3 # If s is shorter than t, swap them to make sure s is longer or equal to t
4 # This helps in reducing further checks
5 if len(s) < len(t):
6 return self.isOneEditDistance(t, s)
7
8 # Extract lengths of both strings.
9 len_s, len_t = len(s), len(t)
10
11 # There cannot be a one edit distance if the length difference is more than 1
12 if len_s - len_t > 1:
13 return False
14
15 # Iterate through both strings
16 for idx in range(len_t):
17 # If the characters at current position are different,
18 # It must either be a replace operation when lengths are same,
19 # Or it must be an insert operation when lengths are different.
20 if s[idx] != t[idx]:
21 if len_s == len_t:
22 # The remainder of the strings after this character should
23 # be the same if it is a replace operation.
24 return s[idx + 1:] == t[idx + 1:]
25 else:
26 # In case of insert operation, the remainder of the longer string
27 # starting from the next character should be the same as the
28 # rest of shorter string starting from current character.
29 return s[idx + 1:] == t[idx:]
30
31 # If all previous chars are same, the only possibility for one edit distance
32 # is when the longer string has one extra character at the end.
33 return len_s == len_t + 1
34
1class Solution {
2
3 public boolean isOneEditDistance(String s, String t) {
4 int lengthS = s.length(), lengthT = t.length();
5
6 // Ensure s is the longer string.
7 if (lengthS < lengthT) {
8 return isOneEditDistance(t, s);
9 }
10
11 // If the length difference is more than 1, it's not one edit distance.
12 if (lengthS - lengthT > 1) {
13 return false;
14 }
15
16 // Check each character to see if there's a discrepancy.
17 for (int i = 0; i < lengthT; ++i) {
18 if (s.charAt(i) != t.charAt(i)) {
19 // If the lengths are the same, the rest of the strings must be equal after this character.
20 if (lengthS == lengthT) {
21 return s.substring(i + 1).equals(t.substring(i + 1));
22 }
23 // If the lengths are not the same, the rest of the longer string must be equal to the rest of the shorter string after this character.
24 return s.substring(i + 1).equals(t.substring(i));
25 }
26 }
27
28 // Covers the case where there is one extra character at the end of the longer string.
29 return lengthS == lengthT + 1;
30 }
31}
32
1class Solution {
2public:
3 // Check if string 's' can be converted to string 't' with exactly one edit
4 bool isOneEditDistance(string s, string t) {
5 int lenS = s.length(), lenT = t.length(); // Use more descriptive variable names
6
7 // Guarantee that 's' is not shorter than 't'
8 if (lenS < lenT) return isOneEditDistance(t, s);
9
10 // If the strings differ in length by more than 1, it can't be one edit
11 if (lenS - lenT > 1) return false;
12
13 // Iterate through characters in both strings
14 for (int i = 0; i < lenT; ++i) {
15 // If characters don't match, check the types of possible one edit
16 if (s[i] != t[i]) {
17 // If lengths are the same, check for replace operation
18 if (lenS == lenT) return s.substr(i + 1) == t.substr(i + 1);
19 // If lengths differ, check for insert operation
20 return s.substr(i + 1) == t.substr(i);
21 }
22 }
23
24 // If all previous characters matched, check for append operation
25 return lenS == lenT + 1;
26 }
27};
28
1// Check if string 's' can be converted to string 't' with exactly one edit
2function isOneEditDistance(s: string, t: string): boolean {
3 let lengthS = s.length; // Length of string 's'
4 let lengthT = t.length; // Length of string 't'
5
6 // Ensure 's' is not shorter than 't'
7 if (lengthS < lengthT) return isOneEditDistance(t, s);
8
9 // If the lengths differ by more than 1, it can't be a single edit
10 if (lengthS - lengthT > 1) return false;
11
12 // Iterate through characters in both strings
13 for (let i = 0; i < lengthT; i++) {
14 // If characters don't match, check the types of possible one edit
15 if (s[i] !== t[i]) {
16 // If lengths are the same, check for replace operation
17 if (lengthS === lengthT) return s.substring(i + 1) === t.substring(i + 1);
18 // If lengths differ, check for insert operation
19 return s.substring(i + 1) === t.substring(i);
20 }
21 }
22
23 // If all previous characters matched, it might be an append operation
24 return lengthS === lengthT + 1;
25}
26
Time and Space Complexity
Time Complexity
The time complexity of the given code is O(N)
where N
is the length of the shorter string between s
and t
. This complexity arises from the fact that we iterate through each character of the shorter string at most once, comparing it with the corresponding character of the longer string. In the worst case, if all characters up to the last are the same, we perform N
comparisons.
Space Complexity
The space complexity of the code is O(1)
. No additional space is required that scales with the input size. The only extra space used is for a few variables to store the lengths of strings and for indices, which does not depend on the size of the input strings.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a min heap?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first