【leetcode】5. Longest Palindromic Substring（Python & C++）
2017-08-25 09:34:47         来源：liuxiao214的博客

## 5. Longest Palindromic Substring

### 5.1 题目描述：

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

Example:

Output: “bab”

Note: “aba” is also a valid answer.

Example:

Input: “cbbd”

Output: “bb”

### 5.3 C++代码：

1、思路一代码（16ms）：

```class Solution92 {
public:
int lengthOfLongestSubstring(string s) {
if (s.length() == 0)
return 0;
if (s.length() == 1)
return 1;
string sub = "";
sub.append(1, s[0]);
int in = 0;
int count = 1;
int temp = 1;
int i = 1;
while (icount)
{
count = temp;
}
i++;
}
return count;
}
};```

2、思路二代码（22ms）：

```class Solution92_1 {
public:
int lengthOfLongestSubstring(string s) {
vectorc(256, -1);
int count = 0;
int first = -1;
for (int i = 0; i < s.length();i++)
{
if (c[s[i]]>first)
first = c[s[i]];
c[s[i]] = i;
count = count > (i - first) ? count : (i - first);
}
return count;
}
};```

### 5.4 Python代码：

1、思路一代码（112ms）：

```class Solution1(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
if len(s)==0:
return 0
if len(s)==1:
return 1
count=1
temp=1
sub=""+s[0]
f=0
for i in range(1,len(s)):
if sub.find(s[i])==-1:
sub=sub+s[i]
temp+=1
else:
f=sub.find(s[i])+1
sub=sub[f::]+s[i]
temp=temp-f+1
if temp>count:
count=temp
return count    ```

2、思路二代码（96ms）：

```class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
a=[-1]*256
count=0
first=-1
for i in range(len(s)):
if a[ord(s[i])]>first:
first=a[ord(s[i])]
a[ord(s[i])]=i
count=max(count,(i-first))
return count```

3、思路三代码（102ms）：

```class Solution2(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
a={}
count=0
first=-1
for i in range(len(s)):
if s[i] in a and a[s[i]]>first:
first=a[s[i]]
a[s[i]]=i
count=max(count,(i-first))
return count```