当前位置： 面试刷题>> 一次编辑距离 (经典算法题500道)
### 题目描述补充
题目：**计算字符串的一次编辑距离**
一次编辑距离（又称Levenshtein距离，但在这里特指距离为1的情况）是指将一个字符串转换成另一个字符串所需的最少单字符编辑操作次数，其中编辑操作包括插入一个字符、删除一个字符或替换一个字符。现在，给定两个字符串`str1`和`str2`，要求判断这两个字符串是否可以通过一次编辑操作相互转换，如果可以，则返回`true`，否则返回`false`。
### 示例
- 输入：`str1 = "abc"`, `str2 = "abd"`
- 输出：`true`（因为可以通过替换`c`为`d`来实现转换）
- 输入：`str1 = "apple"`, `str2 = "app"`
- 输出：`true`（因为可以通过删除`le`来实现转换）
- 输入：`str1 = "hello"`, `str2 = "world"`
- 输出：`false`（因为无法通过一次编辑操作实现转换）
### PHP 代码示例
```php
function isOneEditDistance($str1, $str2) {
$len1 = strlen($str1);
$len2 = strlen($str2);
// 如果长度差大于1，则无法通过一次编辑转换
if (abs($len1 - $len2) > 1) {
return false;
}
// 如果长度相等，则只能替换
if ($len1 === $len2) {
$diffCount = 0;
for ($i = 0; $i < $len1; $i++) {
if ($str1[$i] !== $str2[$i]) {
$diffCount++;
if ($diffCount > 1) {
return false;
}
}
}
return $diffCount === 1;
}
// 长度不等时，决定是删除还是插入
$short = $len1 < $len2 ? $str1 : $str2;
$long = $len1 >= $len2 ? $str1 : $str2;
$i = 0;
$j = 0;
$diffCount = 0;
while ($i < strlen($short) && $j < strlen($long)) {
if ($short[$i] !== $long[$j]) {
$diffCount++;
if ($diffCount > 1) {
return false;
}
// 跳过长字符串中的当前字符，模拟删除或插入操作
$j++;
} else {
$i++;
$j++;
}
}
// 如果还需要继续遍历长字符串（即长度差为1），则可以通过一次删除或插入完成
return $diffCount === 1;
}
// 测试
echo isOneEditDistance("abc", "abd") ? "true" : "false"; // 输出 true
echo PHP_EOL;
echo isOneEditDistance("apple", "app") ? "true" : "false"; // 输出 true
echo PHP_EOL;
echo isOneEditDistance("hello", "world") ? "true" : "false"; // 输出 false
```
### Python 代码示例
```python
def isOneEditDistance(str1, str2):
len1, len2 = len(str1), len(str2)
# 如果长度差大于1，则无法通过一次编辑转换
if abs(len1 - len2) > 1:
return False
# 遍历字符串
i, j = 0, 0
diff_count = 0
while i < len1 and j < len2:
if str1[i] != str2[j]:
diff_count += 1
# 如果已经有一次不同，则决定是删除/插入还是替换
if diff_count > 1:
return False
# 长度不等时，跳过长字符串的当前字符
if len1 != len2:
if len1 < len2:
j += 1
else:
i += 1
else:
i += 1
j += 1
# 检查是否还有剩余未检查的字符（只可能在长度不等的字符串中存在）
return diff_count == 1 or (len1 != len2 and diff_count == 0)
# 测试
print(isOneEditDistance("abc", "abd")) # 输出 True
print(isOneEditDistance("apple", "app")) # 输出 True
print(isOneEditDistance("hello", "world")) # 输出 False
```
### JavaScript 代码示例
```javascript
function isOneEditDistance(str1, str2) {
const len1 = str1.length;
const len2 = str2.length;
// 如果长度差大于1，则无法通过一次编辑转换
if (Math.abs(len1 - len2) > 1) {
return false;
}
let i = 0, j = 0, diffCount = 0;
while (i < len1 && j < len2) {
if (str1[i] !== str2[j]) {
diffCount++;
// 如果已经有一次不同，则决定是删除/插入还是替换
if (diffCount > 1) {
return false;
}
// 长度不等时，跳过长字符串的当前字符
if (len1 !== len2) {
if (len1 < len2) {
j++;
} else {
i++;
}
}
} else {
i++;
j++;
}
}
// 检查是否还有剩余未检查的字符（只可能在长度不等的字符串中存在）
return diffCount === 1 || (len1 !== len2 && diffCount === 0);
}
// 测试
console.log(isOneEditDistance("abc", "abd")); // 输出 true
console.log(isOneEditDistance("apple", "app")); // 输出 true
console.log(isOneEditDistance("hello", "world")); // 输出 false
```
**码小课**网站中有更多相关内容分享给大家学习，包括但不限于算法题解、数据结构、编程语言基础等，欢迎访问学习。