算法实战——字符串问题（四）

第一题：给出一个字符串（假设长度最长为1000），求出它的最长回文子串，你可以假定只有一个满足条件的最长回文串。

最简单的方案，穷举所有可能的子串，判断子串是否为回文，使用一变量记录最大回文长度，若新的回文超过之前的最大回文长度则更新标记变量并记录当前回文的起止索引，最后返回最长回文子串。

Python

class Solution:
 # @param {string} s input string
 # @return {string} the longest palindromic substring
 def longestPalindrome(self, s):
 if not s:
 return ""
 n = len(s)
 longest, left, right = 0, 0, 0
 for i in xrange(0, n):
 for j in xrange(i + 1, n + 1):
 substr = s[i:j]
 if self.isPalindrome(substr) and len(substr) > longest:
 longest = len(substr)
 left, right = i, j
 # construct longest substr
 result = s[left:right]
 return result
 def isPalindrome(self, s):
 if not s:
 return False
 # reverse compare
 return s == s[::-1]

C++

class Solution {
public:
 /**
 * @param s input string
 * @return the longest palindromic substring
 */
 string longestPalindrome(string& s) {
 string result;
 if (s.empty()) return s;
 int n = s.size();
 int longest = 0, left = 0, right = 0;
 for (int i = 0; i < n; ++i) {
 for (int j = i + 1; j <= n; ++j) {
 string substr = s.substr(i, j - i);
 if (isPalindrome(substr) && substr.size() > longest) {
 longest = j - i;
 left = i;
 right = j;
 }
 }
 }
 result = s.substr(left, right - left);
 return result;
 }
private:
 bool isPalindrome(string &s) {
 int n = s.size();
 for (int i = 0; i < n; ++i) {
 if (s[i] != s[n - i - 1]) return false;
 }
 return true;
 }
};

Java

public class Solution {
 /**
 * @param s input string
 * @return the longest palindromic substring
 */
 public String longestPalindrome(String s) {
 String result = new String();
 if (s == null || s.isEmpty()) return result;
 int n = s.length();
 int longest = 0, left = 0, right = 0;
 for (int i = 0; i < n; i++) {
 for (int j = i + 1; j <= n; j++) {
 String substr = s.substring(i, j);
 if (isPalindrome(substr) && substr.length() > longest) {
 longest = substr.length();
 left = i;
 right = j;
 }
 }
 }
 result = s.substring(left, right);
 return result;
 }
 private boolean isPalindrome(String s) {
 if (s == null || s.isEmpty()) return false;
 int n = s.length();
 for (int i = 0; i < n; i++) {
 if (s.charAt(i) != s.charAt(n - i - 1)) return false;
 }
 return true;
 }
}

源码分析

使用left, right作为子串的起止索引，用于最后构造返回结果，避免中间构造字符串以减少开销。