2014
03-23

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

### 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, and there exists one unique longest palindromic substring.

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