LeetCode 5. 最長迴文子串

来源:https://www.cnblogs.com/izhoujie/archive/2020/05/22/12939960.html

我的LeetCode:https://leetcode cn.com/u/ituring/ 我的LeetCode刷題源碼[GitHub]:https://github.com/izhoujie/Algorithmcii LeetCode 5. 最長迴文子串 題目 給定一個字元串 s,找到 s 中最長 ...


我的LeetCode:https://leetcode-cn.com/u/ituring/

我的LeetCode刷題源碼[GitHub]:https://github.com/izhoujie/Algorithmcii

LeetCode 5. 最長迴文子串

題目

給定一個字元串 s,找到 s 中最長的迴文子串。你可以假設 s 的最大長度為 1000。

示例 1:

輸入: "babad"
輸出: "bab"
註意: "aba" 也是一個有效答案。

示例 2:

輸入: "cbbd"
輸出: "bb"

來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/longest-palindromic-substring
著作權歸領扣網路所有。商業轉載請聯繫官方授權,非商業轉載請註明出處。

解題思路

本題有三種思路解法:

  • dp動態規劃
  • 中心擴展
  • Manacher/馬拉車演算法

其中,前兩種時間複雜度都是\(O(n^{2})\),最後一種是\(O(n)\)的,目前最優解;

思路1-dp動態規劃

思路解析:dp的思路是若\([i] == [j]\),那麼讓\([i, j]\)是迴文就必須有\([i + 1] == [j - 1]\)
即dp的動態方程為:

\[dp[i, j] = dp[i + 1, j - 1] and ([i] == [j] || j - i < 3) \]

對於\(j - i < 3\)的解釋:當最後的只剩單個字元時,作為迴文的中心字元免驗證;

演算法複雜度:

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

思路2-中心擴展

思路解析:首先把字元串的所有連續相等的字元都壓縮看為一個字元,那麼對每一個字元嘗試左右擴展迴文長度即可;

核心思想:將所有連續相等的字元看為迴文的最中心字元,避免了對奇偶數的區別計算;

演算法複雜度:

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

思路3-Manacher/馬拉車演算法

待研究...

演算法複雜度:

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

演算法源碼示例

package leetcode;

/**
 * @author ZhouJie
 * @date 2019年12月10日 下午2:30:25 
 * @Description: 5. 最長迴文子串
 *
 */
public class LeetCode_0005 {

}

class Solution_0005 {
	/**
	 * @author ZhouJie
	 * @date 2019年12月10日 下午3:07:18 
	 * @Description: TODO(方法簡述) 
	 * @return String 
	 * @UpdateUser-UpdateDate:[ZhouJie]-[2019年12月10日 下午3:07:18]  
	 * @UpdateRemark:1-動態規劃
	 *
	 */
	public String longestPalindrome_1(String s) {
		int len = 0;
		if (s == null || (len = s.length()) < 2) {
			return s;
		}
		boolean[] p = new boolean[len];
		int[] range = new int[2];
		for (int i = len - 1; i >= 0; i--) {
			for (int j = len - 1; j >= i; j--) {
				// j-i考慮到 像OO和OHO最後中心的奇偶問題
				p[j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || p[j - 1]);
				if (p[j] && (j - i > range[1] - range[0])) {
					range[0] = i;
					range[1] = j;
				}
			}
		}
		return s.substring(range[0], range[1] + 1);
	}

	/**
	 * @author ZhouJie
	 * @date 2019年12月10日 下午3:34:44 
	 * @Description: TODO(方法簡述) 
	 * @return String 
	 * @UpdateUser-UpdateDate:[ZhouJie]-[2019年12月10日 下午3:34:44]  
	 * @UpdateRemark:2-中心擴展--優化後
	 *
	 */
	public String longestPalindrome_2(String s) {
		if (s == null || s.length() < 2) {
			return s;
		}
		int[] range = new int[2];
		char[] cs = s.toCharArray();
		for (int i = 0; i < cs.length; i++) {
			// 把迴文看成中間部分都是同一字元且左右對稱,尋找下一個與當前字元不同的位置
			i = fastMove(cs, i, range);
			// 若剩餘長度不足已知最大長度的一半時,直接跳出迴圈
			// 剩餘長度的下一個起始計算位置為i+1,以為i+1為中心的剩餘最長迴文為(length-1-(i+1))*2+1
			// 即 (lenght-i-2)*2+1,一隻的最大長度為range[1]-range[0]+1
			// 所以判定條件為 (lenght-i-2)*2+1<range[1]-range[0]+1
			// 即(lenght-i-2)*2<range[1]-range[0]
			if ((cs.length - i - 2) * 2 < (range[1] - range[0])) {
				break;
			}
		}
		return s.substring(range[0], range[1] + 1);
	}

	private int fastMove(char[] cs, int low, int[] range) {
		int high = low;
		int len = cs.length;
		// 尋找下一個與low不等的字元
		while (high < len - 1 && cs[high + 1] == cs[low]) {
			high++;
		}
		int nextI = high;
		// 開始校驗左右擴散校驗
		while (low > 0 && high < len - 1 && cs[low - 1] == cs[high + 1]) {
			low--;
			high++;
		}
		if (high - low > range[1] - range[0]) {
			range[0] = low;
			range[1] = high;
		}
		return nextI;
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年5月22日 下午9:47:36 
	 * @param: @param s
	 * @param: @return
	 * @return: String
	 * @Description: 3-Manacher演算法--待研究
	 *
	 */
	public String longestPalindrome_3(String s) {
		return null;
	}
}



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

更多相關文章
  • 設計子程式 子程式一:在指定的位置,用指定的顏色,顯示一個用0結束的字元串 舉例:在屏幕的8行3列,用綠色顯示data段中的字元串 assume cs:code data segment db 'Welcome to masm!',0 data ends code segment start: mo ...
  • [TOC] QuantLib 金融計算——案例之普通利率互換分析(2) 概述 QuantLib 中涉及利率互換的功能大致分為兩大類: 對存續的利率互換合約估值; 根據利率互換合約的成交報價推算隱含的期限結構。 這兩類功能是緊密聯繫的,根據最新報價推算出的期限結構通常可以用來對存續合約進行估值。 本文 ...
  • 1 緩存導致的可見性問題 一個線程對共用變數的修改,另一個線程可以立即看到,這稱之為可見性。 Java記憶體模型規定所有的變數存儲在主記憶體中。每個線程都有自己的工作記憶體,線程在工作記憶體中保存了使用到的主記憶體中變數的副本拷貝,線程對變數的操作必須在工作記憶體中進行,不能直接讀寫主記憶體中的變數。不同線程之間 ...
  • 在項目中經常遇到需要動態編輯特定事物的一組屬性,這時就涉及到新選擇的值與舊值對比更新,記錄在項目中採用的一種方法,主要採用 PHP array_filter() 函數: $delete_array = $add_new_array = array(); $array1 = array( array( ...
  • 檢測是否存在JDK 接下來可以將 開頭的安裝包均卸載即可 下載JDK 在 /opt/soft 內下載jdk "AdoptOpenJDK" 解壓完之後, /opt/module/ ⽬錄中會出現⼀個 的⽬錄 配置JDK環境變數 編輯 ⽂件,在⽂件尾部加⼊如下 JDK 環境配置即可 然後執⾏如下命令讓環境 ...
  • 學習Django有一段時間了,最近剛好寫了一個小項目,用到了前後端交互,剛開始寫前後端交互確實很讓人頭暈目眩呢,下麵我來給大家介紹三種簡單的Django前後端交互的方法吧! 第一種 通過form表單的get或post請求提交到後端的請求方式 <form> <input type='text' nam ...
  • 聲明區域: 變數等可以聲明的區域 例:全局變數的聲明區域為其聲明所在的文件 潛在作用域: 從聲明點開始,到其聲明域的結尾 作用域: 變數對程式而言可見的範圍(即除去潛在作用域中被局部變數等隱藏的區域) ...
  • Hi,大家好,我是明哥。 在自己學習 Golang 的這段時間里,我寫了詳細的學習筆記放在我的個人微信公眾號 《Go編程時光》,對於 Go 語言,我也算是個初學者,因此寫的東西應該會比較適合剛接觸的同學,如果你也是剛學習 Go 語言,不防關註一下,一起學習,一起成長。 我的線上博客:http://g ...
一周排行
  • 一:背景 1. 講故事 曾今在項目中發現有同事自定義結構體的時候,居然沒有重寫Equals方法,比如下麵這段代碼: static void Main(string[] args) { var list = Enumerable.Range(0, 1000).Select(m => new Point ...
  • 最近一個朋友有個關於素數的小東西要寫一下,素數是什麼呢?除了1和他本身不能被其他數整除,那麼這個數就是素數,1除外哦。我們知道概念那就很簡單了,直接代碼擼起。 ...
  • 前言 在開發編程中,我們經常會遇到功能非常相似的功能模塊,只是他們的處理的數據不一樣,所以我們會分別採用多個方法來處理不同的數據類型。但是這個時候,我們就會想一個問題,有沒有辦法實現利用同一個方法來傳遞不同種類型的參數呢? 這個時候,泛型也就因運而生,專門來解決這個問題的。 泛型是在C 2.0就推出 ...
  • 本文章主要用於介紹在Asp.Net Mvc(C#)中使用Fleck製作一個Html5的即時聊天室,含有完整代碼和演示Demo。 ...
  • 出庫單的功能。能學習了出庫單管理之後,WMS的 主體功能算是完成了。當然一個成熟的WMS還包括了盤點,報表,策略規則,移庫功能及與其他系統(ERP、TMS等)的介面,實現無縫集成,打破信息孤島,讓數據實時、準確和同步。 ...
  • Data StructureThere're two types of variables in C#, reference type and value type.Enum:enum Color{Red=0,Green=1}//equals to enum Color{Red,//start fr... ...
  • 0. 前言 該項目使用Maven進行管理和構建,所以需要預先配置好Maven。嗯,在這個系列里就不做過多的介紹了。 1. 創建項目 先創建一個pom.xml 文件,添加以下內容: <?xml version="1.0" encoding="UTF-8"?> <project xmlns="http: ...
  • API 概述 API(Application Programming Interface),應用程式編程介面。 Java API是一本程式員的 字典 ,是JDK中提供給我們使用的類的說明文檔。 這些類將底層的代碼實現封裝了起來,我們不需要關心這些類是如何實現的,只需要學習這些類如何使用即可。 所以我 ...
  • 女程式員是這麼徵婚的: SELECT * FROM 男人們 WHERE 未婚=true and 同性戀=false and 有房=true and 有車=true and 條件 in (帥氣,紳士,大度,氣質,智慧,溫柔,體貼,會浪漫,活潑,可愛,最好還能帶孩子) and 年齡 between(24 ...
  • 有很多剛學習軟體測試的小伙伴,都會在網路上找尋各種學習資料,去提升自己的專業技能水平。因此,我決定定期分享我整理收集的一些軟體測試的測試工具下載、面試寶典、視頻教學合集。都整理好了,有需要的可以關註我(獲取方式在文末) 軟體測試的學習,不止是基礎理論,還需要學習測試工具的用法,如介面工具Postma ...