Given two strings s and t, determine if they are both one edit distance apart.
Note:
There are 3 possiblities to satisify one edit distance apart:
- Insert a character into s to get t
- Delete a character from s to get t
- Replace a character of s to get t
Example 1:
Input: s = "ab", t = "acb" Output: true Explanation: We can insert 'c' into s to get t.
Example 2:
Input: s = "cab", t = "ad" Output: false Explanation: We cannot get t from s by only one step.
Example 3:
Input: s = "1203", t = "1213" Output: true Explanation: We can replace '0' with '1' to get t.
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 | class Solution { public: bool isOneEditDistance(string s, string t) { int ns = s.size(); int nt = t.size(); if(abs(ns-nt)>1 || s==t) return false; if(ns==nt){ int ct = 0; for(int i=0; i<ns; ++i){ if(s[i]!=t[i]) ct++; if(ct>1) return false; } }else if(ns>nt){ int i=0, j=0; while(i<ns && j<nt){ if(s[i]!=t[j]){ if(i>j) return false; i++; }else{ i++; j++; } } }else{ return isOneEditDistance(t, s); } return true; } }; |
No comments:
Post a Comment