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.
Example 3:
Input: s = "a", t = "" Output: true
Example 4:
Input: s = "", t = "A" Output: true
Constraints:
0 <= s.length <= 104
0 <= t.length <= 104
s
andt
consist of lower-case letters, upper-case letters and/or digits.
A:
*************递归*****************
class Solution { public: bool isOneEditDistance(string s, string t) { int n1 = s.length(); int n2 = t.length(); if(n1 > n2) return isOneEditDistance(t,s); if(n1==0){ return n2==1; } if(s[0]==t[0]){ return isOneEditDistance(s.substr(1), t.substr(1)); }else{ // not equal if(n1==n2) // replace on first return s.substr(1) == t.substr(1); else // remove the first of longer return s == t.substr(1); } } };不用递归, 直接用两个指针, 这样快一些。
class Solution { public: bool isOneEditDistance(string s, string t) { int n1 = s.length(); int n2 = t.length(); if(n1 > n2) return isOneEditDistance(t,s); if(n1+1<n2) return false; for(int is = 0; is<n1;is++){ if( s[is] != t[is]){ if(n1==n2) return s.substr(is+1) == t.substr(is+1); else return s.substr(is) == t.substr(is+1); } } return n1+1==n2;// for case s="ab" t="abc" } };
就是简单的分情况讨论
public class Solution { public boolean isOneEditDistance(String s, String t) { int n1 = s.length(), n2 = t.length(); if( n1< n2) return n1+1 == n2 && delOneStep(t,s); else if(n1 == n2) return changeOneStep(s,t); else return n1-1 == n2 && delOneStep(s,t); } private boolean changeOneStep(String s, String t){ int nDif = 0; for(int i =0;i<s.length();i++){ if(s.charAt(i) != t.charAt(i)) nDif++; } return nDif==1; } private boolean delOneStep(String sLong, String sShort){ int dif = 0; for(int i = 0;i<sShort.length();i++){ if(sShort.charAt(i)!=sLong.charAt(i+dif)){ if(dif!=0) return false; i--; dif=1; } } return true; } }
Mistakes:
No comments:
Post a Comment