Two concise C++ solution, 44 ms and 4 ms.


  • 6
    string longestPalindrome(string s) 
    {
    	if (s.empty() || 1 == s.size())
    		return s;
    	int i, a, b, mark, sz = s.size();
    	int maxlen = 1;
    	for (i = 0; i < sz && 2 * (sz - i) > maxlen; ++i) //"2 * (sz - i) > maxlen" used to save run time. For if maxlen >= 2*(sz-i), then means already find the longest string.
    	{
    		a = b = i; //'a' and 'b' used to extend compare range, a <= b.
    		for (; b + 1 < sz && s[b] == s[b + 1]; ++b); //skip same characters
    		for (; a > 0 && b + 1 < sz && s[a - 1] == s[b + 1]; --a, ++b);
    		if (b - a + 1 > maxlen)
    		{
    			mark = a;
    			maxlen = b - a + 1;
    		}
    	}
    	return s.substr(mark, maxlen);
    }
    

    Then I have checked other solutions in the forum, find that some small modifies could save lots of run time. Thanks to @hh1985 and his/her brilliant solution: https://leetcode.com/discuss/32204/simple-c-solution-8ms-13-lines

    string longestPalindrome(string s) 
    {
    	if (s.empty() || 1 == s.size())
    		return s;
    	int i, a, b, mark, sz = s.size();
    	int maxlen = 1;
    	for (i = 0; i < sz && 2 * (sz - i) > maxlen;)
    	{
    		a = b = i;
    		for (; b + 1 < sz && s[b] == s[b + 1]; ++b);
    		i = b + 1; //the key step, rather than ++i, i could skip duplicate characters.
    		for (; a > 0 && b + 1 < sz && s[a - 1] == s[b + 1]; --a, ++b);
    		if (b - a + 1 > maxlen)
    		{
    			mark = a;
    			maxlen = b - a + 1;
    		}
    	}
    	return s.substr(mark, maxlen);
    }

  • 0
    G

    a clean and easy solution!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.