161. One Edit Distance π
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 gett
. - Delete exactly one character from
s
to gett
. - Replace exactly one character of
s
with a different character to gett
.
Example 1:
Input: s = "ab", t = "acb" Output: true Explanation: We can insert 'c' into s to get t.
Example 2:
Input: s = "", t = "" Output: false Explanation: We cannot get t from s by only one step.
Constraints:
0 <= s.length, t.length <= 104
s
andt
consist of lowercase letters, uppercase letters, and digits.
Solutions
Solution 1: Discuss Different Cases
Let $m$ represent the length of string $s$, and $n$ represent the length of string $t$. We can assume that $m$ is always greater than or equal to $n$.
If $m-n > 1$, return false directly;
Otherwise, iterate through $s$ and $t$, if $s[i]$ is not equal to $t[i]$:
- If $m \neq n$, compare $s[i+1:]$ with $t[i:]$, return true if they are equal, otherwise return false;
- If $m = n$, compare $s[i:]$ with $t[i:]$, return true if they are equal, otherwise return false.
If the iteration ends, it means that all the characters of $s$ and $t$ that have been iterated are equal, at this time it needs to satisfy $m=n+1$.
The time complexity is $O(m)$, where $m$ is the length of string $s$. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|