Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

題目描述很簡單,就是尋找一個字符串的最大回文。

1.暴力搜索

 窮舉所有的可能,算法復雜度是O(n^3);

2.dp求解

  http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-i.html

3.對稱

這里考慮到每個回文單詞都是對稱的,所以這里可以使用對稱的思想進行解答。分別遍歷以每個字母為中心的回文字符的最大長度,算法復雜度為O(n ^ 2);空間復雜度是

O(1);

 1 class Solution {
 2 public:
 3     string expand(string&s, int l, int h)
 4     {
 5         while((l >= 0) && (h < s.size()) && (s[l] == s[h]))
 6         {
 7             l--; h++;
 8         }
 9         
10         return s.substr(l+1, h-1-l);
11     }
12     
13     string longestPalindrome(string s) {
14         string res = s.substr(0,1);
15         
16         for(int i = 0; i < s.size(); i++)
17         {
18             string p;
19             p = expand(s, i, i);
20             
21             if(p.size() > res.size())
22                 res = p;
23             p = expand(s, i, i+1);
24             
25             if(p.size() > res.size())
26                 res = p;
27         }
28         
29         return res;
30     }
31 };

?

4。Manacher’s Algorithm

http://www.felix021.com/blog/read.php?2040

http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

轉載于:https://www.cnblogs.com/qtalker/p/4422452.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/273313.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/273313.shtml
英文地址,請注明出處:http://en.pswp.cn/news/273313.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Integer 中的緩存類IntegerCache

2014年去某公司筆試的時候遇到這么一道題&#xff1a; public class Test {public static void main(String[] args) {Integer int1 Integer.valueOf("100");Integer int2 Integer.valueOf("100");System.out.println(int1 int2);} } 問打印的結果的多少…

Android動畫及滑動事件沖突解決(轉載)

原文鏈接&#xff1a;http://blog.csdn.net/singwhatiwanna/article/details/38168103 Android開發中動畫和事件處理是程序員邁向高手的必經之路&#xff0c;也是重點和難點。 此篇轉載文章思路清晰&#xff0c;結構合理&#xff0c;用圖文混合的方式完美的講解了動畫和事件沖突…

在main函數前后執行的函數之 C語言

在gcc中&#xff0c;可以使用attribute關鍵字&#xff0c;聲明constructor和destructor&#xff0c;來指定了函數在main之前或之后運行,代碼如下&#xff1a; 1 #include <stdio.h>2 3 __attribute((constructor)) void before_main()4 {5 printf("%s/n",_…

VSTO開發,轉帖

http://www.cnblogs.com/oneivan/p/4243574.html轉載于:https://www.cnblogs.com/xianerwonder/p/4432595.html

PowerDesigner的漢化破解安裝到逆向工程(ORACLE)

一、軟件安裝 1、下載軟件并安裝安裝16.5漢化版下載地址&#xff1a;真正的漢化-PowerDesigner 16.5 漢化&#xff08;包含安裝文件和漢化文件&#xff09; 破解包下載地址&#xff1a;PowerDesigner V16.5 安裝文件 及 破解文件 &#xff08;包含安裝文件和破解文件&#xff0…

JAVA開發隨記

想到一點寫一點&#xff0c;遇到一點補充一點。 1、成員變量 在定義成員變量時盡量不要直接賦值&#xff0c;最好是在初始化信息的時候進行賦值操作。如果需要在屬性定義的時候進行賦值&#xff0c;那么請用final修飾該屬性。錯誤實例 class A extends B {/** 到期日距離當前…

PHP反射ReflectionClass、ReflectionMethod 入門教程

PHP反射ReflectionClass、ReflectionMethod 入門教程 作者&#xff1a;SNSGOU 發布于&#xff1a;2014-03-16 16:44:00 分類&#xff1a;PHP 瀏覽(6145) PHP5 具有完整的反射API&#xff0c;添加對類、接口、函數、方法和擴展進行反向工程的能力。 反射是什么&#xff…

Oracle開發常用知識

一、利用游標實現循環嵌套 在對oracle數據進行操作時我們會經常碰到循環甚至循環嵌套的情況。這個時候游標的作用就體現出來了。 DECLAREvId NUMBER(19);vDate DATE;--a表游標定義CURSOR a_cursor ISSELECT DISTINCT o.employeeId FROM operations o WHERE o.employeeId IS N…

條件控制(if ) ( case)

一&#xff1a;IF應用格式 (1)                  (2)                (3) IF 條件 THEN           IF 條件 THEN            IF 條件1 THEN --代碼塊               --代碼塊          …

使用臨時表解決union和order by不能同時使用的問題

最近遇見了這樣一個問題&#xff0c;有4張表&#xff0c;A&#xff08;單據&#xff09;表&#xff0c;B&#xff08;產品&#xff09;表&#xff0c;C&#xff08;產品類型&#xff09;&#xff0c;D&#xff08;單據產品關聯表&#xff09;。 B表有唯一對應的類型C&#xff…

2.3線性表的鏈式存儲和運算—雙向鏈表

以上討論的單鏈表的結點中只有一個指向其后繼結點的指針域next&#xff0c;因此若已知某結點的指針為p&#xff0c;其后繼結點的指針則為p->next &#xff0c;而找其前驅則只能從該鏈表的頭指針開始&#xff0c;順著各結點的next 域進行&#xff0c;也就是說找后繼的時間性能…

Oracle常用字符串操作

參考&#xff1a; 一、oracle操作字符串&#xff1a;拼接、替換、截取、查找&#xff1b; 二、oracle中的trim函數使用介紹 --字符串去空格 --輸出:a b c; SELECT TRIM( a b c ) || ; FROM dual; SELECT TRIM(BOTH FROM a b c ) || ; FROM dual; --輸出: a …

linux下面安裝maven

maven作為最近比較火的項目管理工具&#xff0c;對項目的jar包及其開元添加相應的插件的管理&#xff0c;很方便。 安裝maven&#xff1a; 在官網上面去下載最新的maven的壓縮包&#xff0c;apache-maven-3.3.1-bin.tar.gz. 將下載的壓縮包保存/usr/local/maven下&#xff0c;進…

Hibernate懶加載問題

剛開始接觸這種數據持久化框架時&#xff0c;使用的是Maybatis&#xff0c;相較于最原始的JDBCSQL模式&#xff0c;Maybatis簡直就是神器&#xff0c;特別是在用過Maybatis動態SQL后&#xff0c;簡直就開始對Maybatis愛不釋手。后來工作要求&#xff0c;又接觸到了Hibernate&am…

實現點擊按鈕后,倒計時60秒才能再次點擊

轉載于:https://www.cnblogs.com/liu201312/p/4447710.html

通過棧(Stack)實現對樹的遍歷

說到數的遍歷樹&#xff0c;長期以來的第一印象都是通過遞歸去實現。然而今天看了某位前輩的代碼&#xff0c;才發現使用棧去實現遍歷是那么簡單。理論上通過數組也是可以實現同等功能的&#xff0c;畢竟Stack也是通過數據去實現的。 package com.sysway.ui.widget;import jav…

設計模式_01_單一原則

設計模式_01_單一原則 package designPatternOf_01; /*** 單一原則示例&#xff1a;動物呼吸* 引入的問題&#xff1a;魚不吸空氣&#xff0c;吸水*/ public class SinglePrinciple_01 {public static void main(String[] args) {Animal animalnew Animal();animal.breath(&quo…

StroyBoard中UICollectionView中添加Header和footer

到Storyboard中&#xff0c;選擇collection view controller中的"Collection View"。在Attributes inspector中&#xff0c;選擇"Section Header"和"Section Footer",一旦選中你就會在屏幕中看到下面的的顯示&#xff1a; 最重要的是&#xff0c…

樹形結構數據匯總查詢解決方案+優化求助

最近遇到一個地區數據匯總的問題&#xff0c;地區下的地址呈樹形結構&#xff0c;&#xff08;簡化結構&#xff09;如A市下有B、C區&#xff0c;B區下有D、E街道。先要查詢所有地區的人數&#xff08;包括子區域&#xff09;&#xff0c;如A的人數直屬A的人數B的人數C的人數D的…

find 是區分大小寫的。對于不區分大小寫的寫法(轉載)

轉自&#xff1a;http://justwinit.cn/post/3633/ 默認情況下&#xff0c;find 是區分大小寫的。對于不區分大小寫的 find&#xff0c;將 -iname 測試替換為 -name 測試。find downloads -iname "*.gif"downloads/.xvpics/Calendar05_enlarged.gifdownloads/lcmgcfe…