频道栏目
首页 > 考试 > 其他 > 正文
【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:

Input: “babad”

Output: “bab”

Note: “aba” is also a valid answer.

Example:

Input: “cbbd”

Output: “bb”

5.2 解题思路:

思路一:首先记录字符串第一个元素为要找的最长无重复子串sub和初始长度count为1,并这是长度临时变量temp。然后依次遍历字符串后面的元素,判断此元素是否在子串sub中,如果不在,则直接将该字符append到sub后面,temp++;否则,获取该元素在sub中的位置p,erase子串sub中前p+1个元素,然后将该元素append到sub后面,temp-p。然后比较count与temp的大小,进行count更新。

思路二:利用vector,因为此次考虑的字符串中只包含字母,所以可以创建一个256大小,初始化为-1的vector,负责记录字符串中每个字符所在的坐标。并初始化一个first为-1,记录最长无重复子串的起始坐标。在每次遍历字符串时,如果vector中记录的该元素的坐标大于first,说明之前子串已经用到过相同的元素值,发现重复,则更新first为该元素坐标。然后将该元素坐标记录到vector中。最后更新一下count,根据当前遍历的坐标i-first与count比较。

思路三:(Python)使用字典,跟思路二相同,只不过代码看起来更加简洁。

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

点击复制链接 与好友分享!回本站首页
上一篇:35. Search Insert Position
下一篇:hdu 2566 暴力枚举+母函数
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站