LeetCode 面試題 01.05. 一次編輯

来源:https://www.cnblogs.com/izhoujie/archive/2020/07/06/13252873.html
-Advertisement-
Play Games

我的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變數了;
步驟:

  1. 逐個對比;
  2. 首次發現不等,則按如下處理並將boolean機會置false;
    • 若前者較長,那麼給後者加1長度;
    • 若後者較長,那麼給前者加1長度;
    • 長度相等,無處理;
  3. 再次遇到不等直接返回false,或無不等返回true;

演算法複雜度:

  • 時間複雜度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
  • 空間複雜度: $ {\color{Magenta}{\Omicron\left(1\right)}} $

思路2-兩側夾逼校驗最終不等部分長度差

因為只有一次機會,那麼:

  1. 從頭到尾對比並記錄位置;
  2. 從尾到頭對比並記錄位置;
  3. 校驗步驟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;
	}

}



您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 1.塊級元素水平垂直居中 方法1 1 <!--(該方法相容ie8以上瀏覽器)--> 2 position: absolute/fixed; 3 left:0; 4 top:0; 5 right: 0; 6 bottom: 0; 7 margin:auto; 方法2: 1 <!--前提條件:必需知道該 ...
  • 在“JavaScript圖形實例:迭代函數系統生成圖形”一文中,我們介紹了採用迭代函數系統(Iterated Function System,IFS)創建分形圖案的一些實例。在該文中,仿射變換函數W的一般形式為 X1=a*X0 + b*Y0 + e Y1=c*X0 + d*Y0 + f 給定不同的I ...
  • First. 什麼是 algolia search? 根據algolia官方網站自我闡述:Algolia是一個托管搜索引擎,提供全文,數字和多面搜索,能夠從第一次擊鍵中提供實時結果。 Algolia強大的API可讓您快速無縫地在網站和移動應用程式中實施搜索。我們的搜索API每月為成千上萬的公司提供數 ...
  • 在“JavaScript圖形實例:SierPinski三角形” 和“JavaScript圖形實例:Levy曲線及其變形”等文章中我們介紹了通過遞歸生成分形圖形的方法。我們可以將繪製的分形圖形每隔一定的時間間隔後,增加遞歸深度重新繪製一次,這樣就可以得到分形圖形的動態生成效果。 1.SierPinsk ...
  • Nuxt 是 Vue 項目伺服器端渲染(SSR)解決方案。而在使用時,就會遇到前後端分離情況下的功能變數名稱或埠不一致導致的跨域問題。本文將介紹如何通過設置代理解決 Nuxt 與 axios 集成的跨域問題。 ...
  • Electron是一個可以使用 JavaScript,HTML 和 CSS 構建跨平臺桌面應用程式的開源框架。 本文主要分享一下採用vue + electron開發桌面程式的搭建過程。 1. 環境準備 這裡採用的是vue-cli3.x,可以通過下麵的指令查看當前vue-cli的版本: vue --v ...
  • #讀後感# 《企業IT架構轉型之道-阿裡巴巴中台戰略思想與架構實戰》鐘華(花名:古謙)編著,阿裡巴巴中間件首席架構師,15年中間件領域行業經驗。 進入新公司第一天,領導就給了這本書,慚愧,剛看完... 一本推動“中台建設”指導性實戰用書,濃縮了10來年的經驗,從架構層面詳細敘述阿裡共用業務事業部:技 ...
  • 抽象工廠模式 優化抽象工廠 非同步工廠 在學習抽象工廠模式前,先來回顧一下前面的簡單工廠和工廠方法模式。簡單工廠的職責非常簡單:構造某個實體類型,然後把實例作為抽象類型返回; 工廠方法模式則進一步抽象出一個抽象的創建者和一個抽象的產品類型,而實際的執行過程是具體工廠創建具體的產品類型,具體工廠和具體產 ...
一周排行
    -Advertisement-
    Play Games
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...