[LeetCode] 161. One Edit Distance 一个编辑距离
LeetCode 一个 编辑 距离 One EDIT Distance
2023-09-27 14:28:37 时间
Given two strings S and T, determine if they are both one edit distance apart.
72. Edit Distance 的类似题目,编辑距离是从一个单词变成另一个单词的变换步骤。变换步骤可以是:插入,删除和替换。所以考虑三种情况:
1. 长度之差大于1,直接返回False
2. 长度之差等于1,长的字符串可去掉一个字符,剩下的字符串相同。
3. 长度之差等于0,两个字符串对应位置的字符只能有一处不同。
Java:
public boolean isOneEditDistance(String s, String t) { if(s==null || t==null) return false; int m = s.length(); int n = t.length(); if(Math.abs(m-n)>1){ return false; } int i=0; int j=0; int count=0; while(i<m&&j<n){ if(s.charAt(i)==t.charAt(j)){ i++; j++; }else{ count++; if(count>1) return false; if(m>n){ i++; }else if(m<n){ j++; }else{ i++; j++; } } } if(i<m||j<n){ count++; } if(count==1) return true; return false; }
Python:
class Solution(object): def isOneEditDistance(self, s, t): """ :type s: str :type t: str :rtype: bool """ if abs(len(s) - len(t)) > 1: return False for i in range(min(len(s), len(t))): if s[i] != t[i]: if len(s) == len(t): return s[i+1:] == t[i+1:] elif len(s) < len(t): return s[i:] == t[i+1:] else: return s[i+1:] == t[i:] return abs(len(s) - len(t)) == 1
Python:
class Solution(object): def isOneEditDistance(self, s, t): m, n = len(s), len(t) if m > n: return self.isOneEditDistance(t, s) if n - m > 1: return False i, shift = 0, n - m while i < m and s[i] == t[i]: i += 1 if shift == 0: i += 1 while i < m and s[i] == t[i + shift]: i += 1 return i == m
C++:
class Solution { public: bool isOneEditDistance(string s, string t) { for (int i = 0; i < min(s.size(), t.size()); ++i) { if (s[i] != t[i]) { if (s.size() == t.size()) return s.substr(i + 1) == t.substr(i + 1); else if (s.size() < t.size()) return s.substr(i) == t.substr(i + 1); else return s.substr(i + 1) == t.substr(i); } } return abs((int)s.size() - (int)t.size()) == 1; } };
类似题目:
[LeetCode] 72. Edit Distance 编辑距离
All LeetCode Questions List 题目汇总
相关文章
- LeetCode每日一练 —— 203. 移除链表元素
- 【LeetCode】零钱兑换 [M](动态规划)
- 【LeetCode】在排序数组中查找元素的第一个和最后一个位置 [M](二分)
- 【LeetCode】不同的子序列 II [H](动态规划)
- 【LeetCode】天际线问题 [H](模拟)
- 【LeetCode】子数组的最小值之和 [M](单调栈)
- LeetCode_动态规划_中等_808.分汤
- LeetCode_动态规划_中等_1277.统计全为 1 的正方形子矩阵
- LeetCode_随机化_困难_710.黑名单中的随机数
- LeetCode_博弈_简单_292.Nim 游戏
- LeetCode_双指针_中等_142.环形链表II
- LeetCode_双指针_二分搜索_简单_392.判断子序列
- LeetCode_字符串_简单_58.最后一个单词的长度
- LeetCode_二分搜索_中等_34.在排序数组中查找元素的第一个和最后一个位置
- LeetCode_双指针_中等_31.下一个排列
- LeetCode·每日一题·1019. 链表中的下一个更大节点·单调栈
- LeetCode·每日一题·2319.判断矩阵是否是一个X矩阵·数学
- LeetCode·每日一题·2283.判断一个数的数字计数是否等于数位的值·模拟
- LeetCode·每日一题·1769.移动所有球到每一个盒子所需的最小操作数·模拟
- 【LeetCode】- Length of Last Word(最后一个单词的长度)
- 补题:LeetCode第263场周赛&&cf 749
- LeetCode-58. 最后一个单词的长度(Goland实现)
- [LeetCode] 556. Next Greater Element III 下一个较大的元素 III
- [LeetCode] 681. Next Closest Time 下一个最近时间点
- [LeetCode] 34. Search for a Range 搜索一个范围(Find First and Last Position of Element in Sorted Array)
- [LeetCode] 110. Balanced Binary Tree 平衡二叉树
- [LeetCode] 102. Binary Tree Level Order Traversal 二叉树层序遍历
- leetcode 34 在排序数组中查找元素的第一个和最后一个位置