C算法&面试题

最长对称子字符串(2)

2016-03-08  本文已影响234人  AwesomeAshe

解法一在<a>http://www.jianshu.com/p/d23c6b0e02e2
中已经写了,这个方法复杂度太高,我们换一个思路:
对称的情况有两种,一种是奇数长度的,我们在一个字符两端个向两边延伸一个字符并判断;
另一种是偶数长度的,在确定初始位置后,也是向两边延伸一个字符然后判断。
满足则继续延伸,不满足移向下一个字符。
这样判断的复杂度降低了,O(1),遍历复杂度还是O(N2)

int getLongestSymmetricalLength_2(char* pstring)
{
    if (!pstring)
        return 0;
    char *pchar = pstring;//pchar moves a char one turn
    int symmtricallen = 1;
    int newlen = 0;

    while (*pchar != '\0')
    {
        //1,substring with odd len
        char* pfirst = pchar - 1;
        char* plast = pchar + 1;

        while (pfirst >= pstring&&*plast != '\0'&&*pfirst == *plast)
//这里判断的方法很简单,每次只增加一个字符,所以只需判断增加的字符是否相等即可
        {
            pfirst--;
            plast++;
        }
        newlen = plast - pfirst;
        if (newlen > symmtricallen) 
            symmtricallen = newlen ;

        //2,even substr len
        char* pfirst = pchar;
        char* plast = pchar + 1;

        while (pfirst >= pstring&&*plast != '\0'&&*pfirst == *plast)
        {
            pfirst--;
            plast++;
        }
        newlen = plast - pfirst;
        if (newlen > symmtricallen)
            symmtricallen = newlen;

        pchar++;
    }

    return symmtricallen;

}
上一篇 下一篇

猜你喜欢

热点阅读