leetcode:5. Longest Palindromic Substring

2019-11-06 06:49:10

字体：大中小

来源：转载

供稿：网友

描述

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: “babad”

Output: “bab”

Note: “aba” is also a valid answer. Example:

Input: “cbbd”

Output: “bb”

思路

遍历字符串s, 遍历索引cur，检测cur两边是不是相等。

代码

class Solution {public: string longestPalindrome(string s) { int size_s = s.size(); int cur = 0, sub_cur = 0,max_palindromic = 1, start_idx = 0; bool is_same = true; while(cur < size_s){ if(s[cur+1] == s[cur]){ sub_cur = 1; is_same = true; while(is_same ){ is_same = (s[cur - sub_cur] == s[cur + sub_cur + 1] && cur - sub_cur>=0) ? true:false; sub_cur++; } if(2*sub_cur - 2> max_palindromic){ start_idx = cur - sub_cur + 2; max_palindromic = 2*sub_cur - 2; } } if(s[cur-1] == s[cur + 1] && cur - 1 >= 0){ sub_cur = 2; is_same = true; while(is_same ){ is_same = (s[cur - sub_cur] == s[cur + sub_cur] && cur - sub_cur >=0) ? true:false; sub_cur++; } if(2*sub_cur - 3> max_palindromic){ start_idx = cur - sub_cur + 2; max_palindromic = 2*sub_cur - 3; } } cur++; } return s.substr(start_idx, max_palindromic); }};

结果

这里写图片描述

反思

今天原计划刷两题的，但是这一题耽误了我太多时间，大概40-50分钟的时候就已经编写出来了，但是一直在找错，最后发现是string的一个接口（substr）没有理解清楚。！！！！谨记，使用别人接口的时候，一定要弄明白参数的每一个含义。

他山之玉

C++ O(n) solutioin

string longestPalindrome(string s) { if (s.empty()) return ""; if (s.size() == 1) return s; int min_start = 0, max_len = 1; for (int i = 0; i < s.size();) { if (s.size() - i <= max_len / 2) break; int j = i, k = i; while (k < s.size()-1 && s[k+1] == s[k]) ++k; // Skip duplicate characters. i = k+1; while (k < s.size()-1 && j > 0 && s[k + 1] == s[j - 1]) { ++k; --j; } // Expand. int new_len = k - j + 1; if (new_len > max_len) { min_start = j; max_len = new_len; } } return s.substr(min_start, max_len);}

java O(n) solution

public String longestPalindrome(String s) { if(s==null){ return ""; } char[] arr = s.toCharArray(); int max = 0; int maxi = 0; int maxj = 0; for(int i = 0; i< arr.length;){ int i1 = getFarestSameElementIndex(arr,i); int dist = getDistance(arr,i,i1); int index1 = i-dist; int index2 = i1 + dist; int l = index2 - index1; if(l>max){ max = l; maxi = index1; maxj = index2; } i = i1+1; } return s.substring(maxi, maxj+1);}PRivate int getDistance(char[] arr,int index1,int index2){ int i1 = index1-1; int i2 = index2+1; int dist = 0; while(i1>=0&&i2<arr.length){ if(arr[i1]==arr[i2]){ dist++; }else{ break; } i1--;i2++; } return dist;}private int getFarestSameElementIndex(char[] arr, int index){ for(int i = index+1;i<arr.length;i++){ if(arr[i]!=arr[index]){ return i-1; } } return arr.length-1;}

python O(n) solution

lass Solution(object): def longestPalindrome(self, s): """ :type s: str :rtype: str """ # make it okay for both odd and even cases T = "^#" + "#".join(list(s)) + "#$" n = len(T) P = [0] * n # C and R are center and right boundary of current farest palindrome C = R = 0 for i in range(1, n-1): P[i] = min(R-i, P[2*C-i]) if R > i else 0 # check palindrome only for possible candidate, key idea why it's O(n) if P[i] + i >= R: while T[i-1-P[i]] == T[i+1+P[i]]: P[i] += 1 # update C and R C, R = i, i + P[i] L, C = max((x, j) for j, x in enumerate(P)) return s[(C - L) >> 1 : (C + L) >> 1]

上一篇：FormBorderStyle.None时，支持改变窗体大小

下一篇：选择排序以及对它的优化