BAT面試算法進階(5)- BAT面試算法進階(5)- 最長回文子串(方法一)
BAT面試算法進階(4)- 無重復字符的最長子串(滑動法優(yōu)化+ASCII碼法)
BAT面試算法進階(3)- 無重復字符的最長子串(滑動窗口法)
BAT面試算法進階(2)- 無重復字符的最長子串(暴力法)
BAT面試算法進階(1)--兩數(shù)之和
# 程序員進階之算法練習(六)- 最大回文子串
小編OS: 今天是我們一起堅持的第六天了,繼續(xù)加油!
回顧一下,昨天我們學習的是回文動態(tài)規(guī)劃處理方法,但是?難道沒有更優(yōu)秀的解決方案嗎?肯定有呀!!!
一.算法題
- 題目
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
- Example
Example1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example2:
Input: "cbbd"
Output: "bb"
二.算法題解讀
- 題目大意:給定一個字符串S,找出S串中最長的回文子串.你可以假設(shè)s的最大長度為1000.
Example1:
輸入: "babad"
輸出: "bab"
注意: "aba" 是一個有效答案.
Example2:
輸入: "cbbd"
輸出: "bb"
三.回文字符串
我們上一篇文分享的不管從時間復雜度還是空間復雜度,都是頗為浪費的? 難道沒有更優(yōu)解決方案?肯定是有的!
四.代碼
string expandAroundCenter(string s, int c1, int c2) {
int l = c1, r = c2;
int n = s.length();
while (l >= 0 && r <= n-1 && s[l] == s[r]) {
l--;
r++;
}
return s.substr(l+1, r-l-1);
}
string longestPalindromeSimple(string s) {
int n = s.length();
if (n == 0) return "";
//單個字符也是回文字符
string longest = s.substr(0, 1);
for (int i = 0; i < n-1; i++) {
string p1 = expandAroundCenter(s, i, i);
if (p1.length() > longest.length())
longest = p1;
string p2 = expandAroundCenter(s, i, i+1);
if (p2.length() > longest.length())
longest = p2;
}
return longest;
}
五.復雜度
時間復雜度: o(N*N)
空間復雜度: O(1)
六.學習建議
大家可以畫10分鐘左右,將代碼的模擬執(zhí)行一遍.即可明白其過程.明天我們會更新一種另外的解決方案哦.
小編OS:
如有疑問,留言即可.胖C會利用空余時間給大家做一個簡單解答的.
持續(xù)更新關(guān)注公眾號!
