首页 > ACM题库 > LeetCode > leetCode-Longest Palindromic Substring(最长回文串)
2014
03-23

leetCode-Longest Palindromic Substring(最长回文串)

Longest Palindromic Substring

难度:4  面试频率 2 (1-5)

题目描述:

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.

链接:http://oj.leetcode.com/problems/longest-palindromic-substring/

分析:

最长回文串也是个常见问题了,解法也比较多。效率最高的是经典的manacher算法(参考:HDU 3068 九度 1528),复杂度O(n),但是用的不多,老是忘掉。还有动态规划 O(n2),中心扩展法O(n2)。个人觉得中心扩展法是比较容易的,其实就模拟一边,两个指针向两个方向扩展,记录下最远能扩展到的距离。代码如下:

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
		if (n <= 1)
			return s;
		int maxlen = 1, k, j, a = 0;
		int l;
		for (int i = 1; i < n;) {
			k = i - 1;
			j = i + 1;
			while (k >= 0 && s[k] == s[i])
				k--;
			while (j < n && s[j] == s[i])
				j++;
			i = j;//这个地方i=j 为了防止 s[i]出现多次,后面的一些判断就是多余。例如 baaaabc, 当i=1,此时 j=5
			//从k和j开始向两边扩展
			while (k >= 0 && j < n && s[k] == s[j]) {
				k--;
				j++;
			}
			l = j - k - 1;
			if (maxlen < l) {
				a = k + 1;
				maxlen = l;
			}
		}
		return s.substr(a, maxlen);
    }
};

  1. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  2. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count