我的LeetCode:https://leetcode-cn.com/u/ituring/ 我的LeetCode刷題源碼[GitHub]:https://github.com/izhoujie/Algorithmcii LeetCode 題目 字元串有三種編輯操作:插入一個字元、刪除一個字元或者替換 ...
我的LeetCode:https://leetcode-cn.com/u/ituring/
我的LeetCode刷題源碼[GitHub]:https://github.com/izhoujie/Algorithmcii
LeetCode
題目
字元串有三種編輯操作:插入一個字元、刪除一個字元或者替換一個字元。 給定兩個字元串,編寫一個函數判定它們是否只需要一次(或者零次)編輯。
示例 1:
輸入:
first = "pale"
second = "ple"
輸出: True
示例 2:
輸入:
first = "pales"
second = "pal"
輸出: False
來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/one-away-lcci
著作權歸領扣網路所有。商業轉載請聯繫官方授權,非商業轉載請註明出處。
解題思路
思路1-記錄是否編輯過
因為只有一次編輯機會,所以使用一個boolean變數來表示這個機會,當然如果是多次機會,那麼就得換用int變數了;
步驟:
- 逐個對比;
- 首次發現不等,則按如下處理並將boolean機會置false;
- 若前者較長,那麼給後者加1長度;
- 若後者較長,那麼給前者加1長度;
- 長度相等,無處理;
- 再次遇到不等直接返回false,或無不等返回true;
演算法複雜度:
- 時間複雜度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空間複雜度: $ {\color{Magenta}{\Omicron\left(1\right)}} $
思路2-兩側夾逼校驗最終不等部分長度差
因為只有一次機會,那麼:
- 從頭到尾對比並記錄位置;
- 從尾到頭對比並記錄位置;
- 校驗步驟1和2中各自對應的位置差值,必須小於2;
演算法複雜度:
- 時間複雜度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空間複雜度: $ {\color{Magenta}{\Omicron\left(1\right)}} $
演算法源碼示例
package leetcode;
/**
* @author ZhouJie
* @date 2020-7-6 0:31:36
* @Description: 面試題 01.05. 一次編輯
*
*/
public class LeetCode_Satine_01_05 {
/**
* @author: ZhouJie
* @date: 2020-7-6 0:32:45
* @param: @param first
* @param: @param second
* @param: @return
* @return: boolean
* @Description: 1-記錄是否編輯過;
*
*/
public boolean oneEditAway_1(String first, String second) {
if (first == null && second == null) {
return true;
}
int len1 = first.length();
int len2 = second.length();
int t = len1 - len2;
if (t > 1 || t < -1) {
return false;
}
int i = 0, j = 0;
// 只有一次機會
boolean onceChance = true;
while (i < len1 && j < len2) {
if (first.charAt(i) != second.charAt(j)) {
if (onceChance) {
// first較長
if (t == 1) {
j--;
// second較長
} else if (t == -1) {
i--;
}
onceChance = !onceChance;
} else {
return onceChance;
}
}
i++;
j++;
}
return true;
}
/**
* @author: ZhouJie
* @date: 2020-7-6 1:51:04
* @param: @param first
* @param: @param second
* @param: @return
* @return: boolean
* @Description: 2-兩側夾逼校驗最終不等部分長度差;
*
*/
public boolean oneEditAway_2(String first, String second) {
if (first == null && second == null) {
return true;
}
int len1 = first.length();
int len2 = second.length();
int t = len1 - len2;
if (t > 1 || t < -1) {
return false;
}
int k = 0;
while (k < len1 && k < len2 && first.charAt(k) == second.charAt(k)) {
k++;
}
len1--;
len2--;
while (len1 >= k && len2 >= k && first.charAt(len1) == second.charAt(len2)) {
len1--;
len2--;
}
return (len1 - k) < 1 && (len2 - k) < 1;
}
}