LeetCode算法入門- Longest Palindromic Substring-day5

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.

Example 1:

Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.
Example 2:

Input: “cbbd”
Output: “bb”

最便捷的方法：時間復雜度0（n），空間復雜度0（1）
使用中心擴散法：我們可以從一個中心點出發，然后慢慢向左右兩邊進行擴散，然后獲取當前其最長字符串，最后取出最終最長的字符串。
不過這樣的話就要分成兩種情況：因為中心對稱有兩種，一種是奇數對稱，一種是偶數對稱

class Solution {String longestStr = "";public String longestPalindrome(String s) {for(int i = 0; i < s.length(); i++){//奇數helper(s,i,0);//偶數helper(s,i,1);}return longestStr;}public void helper(String s, int start, int offset){int left = start;int right = start + offset;while(left >= 0 && right < s.length() &&s.charAt(left) == s.charAt(right)){left--;right++;}//取當前最大字符串，substring方法：左邊取，右邊不取，這里left記得加1，right不變，因為上面left減了1String curLongest = s.substring(left + 1, right);if(curLongest.length() > longestStr.length())longestStr = curLongest;} }

總結

以上是生活随笔為你收集整理的LeetCode算法入门- Longest Palindromic Substring-day5的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。