LeetCode 161. One Edit Distance--Python,Java,C++解法

---

LeetCode题解专栏：LeetCode题解 LeetCode 所有题目总结：LeetCode 所有题目总结 大部分题目C++，Python，Java的解法都有。

---

题目地址：One Edit Distance - LeetCode

---

此题链接：One Edit Distance - LeetCode 这道题目进阶版本Edit Distance - LeetCode 文章地址:LeetCode 72. Edit Distance - zhangpeterx的博客 - 博客

---

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 tDelete a character from s to get tReplace 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.

---

如果s与t是One Edit Distance，那么s与t要么长度相等，做一次替换，要么长度差一，做删除或者插入。 Python解法如下：

class Solution: def isOneEditDistance(self, s: str, t: str) -> bool: lenS=len(s) lenT=len(t) if lenS>lenT: s,t=t,s lenS,lenT=lenT,lenS if lenS==lenT: count=0 for i in range(0,lenS): if s[i]!=t[i]: count+=1 if count>=2: break if count==1: return True else: return False elif lenT-lenS>=2: return False else: flag=0 for i in range(0,lenT): if i==lenT-1 and flag==0: return True elif s[i-flag]!=t[i]: if flag==0: flag=1 else: return False return True

Java解法如下：

class Solution { public boolean isOneEditDistance(String s, String t) { int ns = s.length(); int nt = t.length(); // Ensure that s is shorter than t. if (ns > nt) return isOneEditDistance(t, s); // The strings are NOT one edit away distance // if the length diff is more than 1. if (nt - ns > 1) return false; for (int i = 0; i < ns; i++) if (s.charAt(i) != t.charAt(i)) // if strings have the same length if (ns == nt) return s.substring(i + 1).equals(t.substring(i + 1)); // if strings have different lengths else return s.substring(i).equals(t.substring(i + 1)); // If there is no diffs on ns distance // the strings are one edit away only if // t has one more character. return (ns + 1 == nt); } }

C++解法如下：

class Solution { public: bool isOneEditDistance(string s, string t) { int m = s.size(), n = t.size(); if (m > n) { return isOneEditDistance(t, s); } for (int i = 0; i < m; i++) { if (s[i] != t[i]) { if (m == n) { return s.substr(i + 1) == t.substr(i + 1); } return s.substr(i) == t.substr(i + 1); } } return m + 1 == n; } };