难度: 中等 | 标签: 字符串 双指针

1. 题目描述

https://leetcode.cn/problems/one-away-lcci/
字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。

示例 1:
输入:
first = “pale”
second = “ple”
输出: True
示例 2:
输入:
first = “pales”
second = “pal”
输出: False

通过次数: 44,201 | 提交次数: 136,132

2. 题解

2022-05-13 AC, 咱的想法就是暴力模拟, 大佬的写法就是简洁优雅

  1. <?php
  2. /**
  3.  * Created by PhpStorm
  4.  * User: jtahstu
  5.  * Time: 2022/5/13 0:33
  6.  * Des: 面试题 01.05. 一次编辑
  7.  *      https://leetcode.cn/problems/one-away-lcci/
  8.  *      字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。
  9.  */
  11. class Solution
  12. {
  14.     /**
  15.      * @param String $first
  16.      * @param String $second
  17.      * @return Boolean
  18.      */
  19.     function oneEditAway($first, $second)
  20.     {
  21.         $f_len = strlen($first);
  22.         $s_len = strlen($second);
  23.         if (abs($f_len - $s_len) > 1) return false;
  24.         if ($first == $second) return true;
  25.         if ($f_len > $s_len) {
  26.             list($first, $second) = [$second, $first];
  27.             list($f_len, $s_len) = [$s_len, $f_len];
  28.         }
  29.         if (!$first) return true;
  30.         if ($s_len == $f_len + 1) { //插入或删除字符
  31.             for ($i = 0; $i < $s_len; $i++) {
  32.                 $s = substr($second, 0, $i) . substr($second, $i + 1, $s_len - $i);
  33.                 echo $s . PHP_EOL;
  34.                 if ($s == $first) {
  35.                     return true;
  36.                 }
  37.             }
  38.         } else { //替换字符
  39.             for ($i = 0; $i < $s_len; $i++) {
  40.                 $s = $second;
  41.                 $s[$i] = $first[$i];
  42.                 if ($s == $first) {
  43.                     return true;
  44.                 }
  45.             }
  46.         }
  47.         return false;
  48.     }
  49. }
  51. var_dump((new Solution)->oneEditAway("pale", "pal"));
  52. var_dump((new Solution)->oneEditAway("pales", "pal"));
  53. var_dump((new Solution)->oneEditAway("a", "b"));
  55. /**
  56.  * 执行用时：8 ms, 在所有 PHP 提交中击败了80.65%的用户
  57.  * 内存消耗：18.7 MB, 在所有 PHP 提交中击败了41.94%的用户
  58.  * 通过测试用例：1146 / 1146
  59.  */
  61. //这个写法比较流弊, 都+1是替换, second+1是删除, first+1是插入
  62. //class Solution:
  63. //    def oneEditAway(self, first: str, second: str) -> bool:
  64. //        m,n=len(first),len(second)
  65. //        if abs(m-n)>1:
  66. //            return False
  67. //        for i in range(min(m,n)):
  68. //            if first[i]!=second[i]:
  69. //                return first[i+1:]==second[i+1:] or first[i:]==second[i+1:] or first[i+1:]==second[i:]
  70. //        return True