我的生活记录

leetcode-cn.com（领扣），一个不错的代码练习网站

第五题   https://leetcode-cn.com/problems/longest-palindromic-substring/description/

这次做的不好，并且想不出办法来优化。打败 22.61 %选手。

原因可能是使用了很多sting的库函数来检查长度。

题目：

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

示例 1：

输入: "babad"输出: "bab"注意: "aba"也是一个有效答案。

示例 2：

输入: "cbbd"输出: "bb"

我的答案：

class Solution {
public:
    int lengths = 0 ;
    int ifok(char *str, int n)
    {
        //指向字符串首尾的指针
        char *front = str;
        char *back = str + n - 1;

        if(str==NULL||n<1)
        {
            return 0;
        }
        while (front<back)
        {
            if (*front != *back)
            {
                return 0;
            }
            front++;
            back--;
        }

        return 1;	
    }
    
    
    void writeout(char *m,char *n,string &out)
    {   char *a=m;
        char *b=n;
        out="";
        while(a != b + 1)
        {out.append(1,*a);a++;}
        
    }
    
    string longestPalindrome(string s)
    {   
        string out;
        if (s.length() == 0){return s;}
        char *start = &s[0];
        char *end = &s[s.length()-1];
        char *e = end;
        for(;start!=end+1;start++)
        {
            for(;e!=start-1;e--)
            {   if(end-start+1<lengths){break;}
                while(ifok(start,e-start+1)==1&&e-start+1>lengths)
                {
                    lengths=e-start+1;
                    writeout(start,e,out);
                    
                }
                
            }
            e=end;
        }
        return out;
    }
};

打赏

微信扫一扫，打赏作者吧～