首页 > 代码库 > leetcode[161] One Edit Distance
leetcode[161] One Edit Distance
判断两个字符串的编辑距离是不是1.
关于编辑距离可以参见之前有一题leetcode[72] Edit Distance
思路：
如果字符串相差2个以及以上长度，那么肯定不止1，直接false
如果字符串长度相等，那么判断对应位置不同的字符数是不是1即可。
如果字符串长度相差1，那么肯定是要在长的那个串删掉一个，所以两个字符串一起加加，一旦遇到一个不同，那么剩下的子串就要是一样，否则就是不止一个不同，false。
bool isOneDifL(string s, string t) { for (int i = 0; i < s.size(); i++) { if (s[i] == t[i]) continue; return s.substr(i) == t.substr(i+1); } return true; // 说明前面的都相等只有最后一个不匹配 } bool isSameLen(string s, string t) { int cnt = 0; for (int i = 0; i < s.size(); i++) { if (s[i] != t[i]) cnt++; } return cnt == 1; } bool isOneEditDistance(string s, string t) { if (abs(s.size() - t.size()) > 1) return false; if (s.size() == t.size()) return isSameLen(s, t); else if (s.size() < t.size()) return isOneDifL(s, t); else return isOneDifL(t, s); }
还可以参见一个函数搞定的，巧妙的合在一起
bool isOneEditDistance2(string s, string t){ if (s.length() > t.length()) { swap(s,t); } if (t.length() - s.length() > 1) { return false; } bool have = false; for (int i = 0, j = 0; i < s.length(); ++i,++j){ if (s[i] != t[j]) { if (have) { return false; } have = true; if (s.length() < t.length()) { --i; } } } return (have) || (s.length() < t.length()); }
leetcode[161] One Edit Distance
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。