手机网站微信分享代码,搭建公司介绍网站,网站开发工作好不好,做自媒体的素材网站文章目录 一、题目二、C# 题解法一#xff1a;从第一个不同位置处判断后续相同子串法二#xff1a;前后序遍历判断第一个不同字符的位置关系 优化法一法二 一、题目 字符串有三种编辑操作:插入一个英文字符、删除一个英文字符或者替换一个英文字符。 给定两个字符串#xff… 文章目录 一、题目二、C# 题解法一从第一个不同位置处判断后续相同子串法二前后序遍历判断第一个不同字符的位置关系 优化法一法二 一、题目 字符串有三种编辑操作:插入一个英文字符、删除一个英文字符或者替换一个英文字符。 给定两个字符串编写一个函数判定它们是否只需要一次(或者零次)编辑。 点击此处跳转题目。
示例 1: 输入: first “pale” second “ple” 输出: True 示例 2: 输入: first “pales” second “pal” 输出: False 二、C# 题解
法一从第一个不同位置处判断后续相同子串 由题可知在不同位置处左方和右方的子串应相同。因此先寻找到第一个不同的字符判断其后方子串是否一致 替换IsSame(first, i 1, second, j 1) h o r s e ( f i r s t ) i : ↑ h o r t e ( s e c o n d ) j : ↑ \begin{array}{l} h o r s e (first)\\ i: \uparrow \\\\ h o r t e (second)\\ j: \uparrow \end{array} i:j:hhoorrs↑t↑ee(first)(second) 插入IsSame(first, i, second, j 1) h o r s e ( f i r s t ) i : ↑ h o r t s e ( s e c o n d ) j : ↑ \begin{array}{l} h o r s e (first)\\ i: \uparrow \\\\ h o r t s e (second)\\ j: \uparrow \end{array} i:j:hhoorrs↑t↑ese(first)(second) 删除IsSame(first, i 1, second, j) h o r s e ( f i r s t ) i : ↑ h o r e ( s e c o n d ) j : ↑ \begin{array}{l} h o r s e (first)\\ i: \uparrow \\\\ h o r e (second)\\ j: \uparrow \end{array} i:j:hhoorrs↑e↑e(first)(second)
public class Solution {// 方法从第一个不同位置处判断后续相同子串public bool OneEditAway(string first, string second) {int i 0, j 0; // 双指针i 遍历 firstj 遍历 second可以用一个指针代替因为 i 时刻等于 j// 前序遍历寻找第一处不同while (i first.Length j second.Length) { if (first[i] ! second[j]) break;i; j;}// 判断字符串相等if (i first.Length j second.Length) return true;// 判断后续内容是否相同return IsSame(first, i 1, second, j) || IsSame(first, i, second, j 1) || IsSame(first, i 1, second, j 1);}// 判断从位置 i 开始的 first 字符串和从位置 j 开始的 second 字符串是否相等public bool IsSame(string first, int i, string second, int j) {// 判断界限内每个字符是否相等while (i first.Length j second.Length) {if (first[i] ! second[j]) return false;i; j;}// 判断是否都到达了字符串末尾避免出现其中一个字符串仍有后续内容的情况return i first.Length j second.Length;}
}时间复杂度 O ( m a x ( m , n ) ) O(max(m,n)) O(max(m,n))其中 m , n m,n m,n 分别为字符串 f i r s t , s e c o n d first, second first,second 的长度。空间复杂度 O ( 1 ) O(1) O(1)。
法二前后序遍历判断第一个不同字符的位置关系 使用前序遍历找出两个字符串不同字符的第一个位置 firstDif1, firstDif2再用后序遍历找出两个字符串不同字符的第一个位置 lastDif1, lastDif2。依据这四个位置的关系来判断字符串的关系 相等firstDif1 first.Length lastDif1 -1 至于 firstDif2 second.Length lastDif2 -1 可以不判断因为必定存在。 h o r s e l a s t D i f 1 : ↑ ↑ : f i r s t D i f 1 h o r s e l a s t D i f 2 : ↑ ↑ : f i r s t D i f 2 \begin{array}{l} h o r s e \\ lastDif1: \green\uparrow \red\uparrow :firstDif1\\\\ h o r s e \\ lastDif2: \green\uparrow \red\uparrow :firstDif2 \end{array} lastDif1:lastDif2:↑↑hhoorrssee↑↑:firstDif1:firstDif2 替换firstDif1 lastDif1 firstDif2 lastDif2 h o r s e f i r s t D i f 1 : ↑ ↑ : l a s t D i f 1 h o r t e f i r s t D i f 2 : ↑ ↑ : l a s t D i f 2 \begin{array}{l} h o r s e \\ firstDif1: \red\uparrow\green\uparrow :lastDif1\\\\ h o r t e \\ firstDif2: \red\uparrow\green\uparrow :lastDif2 \end{array} firstDif1:firstDif2:hhoorrs↑↑t↑↑ee:lastDif1:lastDif2 插入firstDif1 - 1 lastDif1 firstDif2 lastDif2 h o r s e l a s t D i f 1 : ↑ ↑ : f i r s t D i f 1 h o r t s e f i r s t D i f 2 : ↑ ↑ : l a s t D i f 2 \begin{array}{l} h o r s e \\ lastDif1: \green\uparrow \red\uparrow :firstDif1\\\\ h o r t s e \\ firstDif2: \red\uparrow\green\uparrow :lastDif2 \end{array} lastDif1:firstDif2:hhoor↑rs↑t↑↑ese:firstDif1:lastDif2 删除firstDif1 lastDif1 firstDif2 - 1 lastDif2 h o r s e f i r s t D i f 1 : ↑ ↑ : l a s t D i f 1 h o r e l a s t D i f 2 : ↑ ↑ : f i r s t D i f 2 \begin{array}{l} h o r s e \\ firstDif1: \red\uparrow\green\uparrow :lastDif1\\\\ h o r e \\ lastDif2: \green\uparrow \red\uparrow :firstDif2 \end{array} firstDif1:lastDif2:hhoorr↑s↑↑e↑e:lastDif1:firstDif2
public class Solution {// 前后序遍历判断第一个不同字符的位置关系public bool OneEditAway(string first, string second) {int firstDif1, firstDif2, lastDif1, lastDif2;FirstDiffer(first, out firstDif1, second, out firstDif2);LastDiffer(first, out lastDif1, second, out lastDif2);// 相等if (firstDif1 first.Length lastDif1 -1) return true;// 替换if (firstDif1 lastDif1 firstDif2 lastDif2) return true;// 插入if (firstDif1 - 1 lastDif1 firstDif2 lastDif2) return true;// 删除if (firstDif1 lastDif1 firstDif2 - 1 lastDif2) return true;return false;}// 前序寻找第一个不同字符的位置public void FirstDiffer(string first, out int firstDif1, string second, out int firstDif2) {firstDif1 firstDif2 0;while (firstDif1 first.Length firstDif2 second.Length) {if (first[firstDif1] ! second[firstDif2]) return;firstDif1; firstDif2;}}// 后序寻找第一个不同字符的位置public void LastDiffer(string first, out int lastDif1, string second, out int lastDif2) {lastDif1 first.Length - 1;lastDif2 second.Length - 1;while (lastDif1 0 lastDif2 0) {if (first[lastDif1] ! second[lastDif2]) return;lastDif1--; lastDif2--;}}
}时间复杂度 O ( m a x ( m , n ) ) O(max(m,n)) O(max(m,n))其中 m , n m,n m,n 分别为字符串 f i r s t , s e c o n d first, second first,second 的长度。空间复杂度 O ( 1 ) O(1) O(1)。 优化 看到了题解中有大佬使用手段确保 first 长度不大于 second写法很好借鉴一下。由于此题插入和删除具有对称性因此可以做出如下优化
法一 可以不判断删除的情况减少一次遍历。
public class Solution {public bool OneEditAway(string first, string second) {if (first.Length second.Length) // 确保 first 长度不大于 secondreturn OneEditAway(second, first);int i 0, j 0; while (i first.Length j second.Length) { if (first[i] ! second[j]) break;i; j;}// 判断字符串相等只用判断 second 是否达到末端即可if (j second.Length) return true;// 判断后续内容是否相同少判断一种情况return IsSame(first, i, second, j 1) || IsSame(first, i 1, second, j 1);}public bool IsSame(string first, int i, string second, int j) {while (i first.Length j second.Length) {if (first[i] ! second[j]) return false;i; j;}return i first.Length j second.Length;}
}法二 法二没有必要了因为减少“删除”的情况只减少了一次 int 比较的判断而可能多带来一次参数拷贝first 和 second 互换传入参数。
