Accepted 4ms c++ solution.


  • 48
    class Solution {
    public:
        std::string longestPalindrome(std::string s) {
            if (s.size() < 2)
                return s;
            int len = s.size(), max_left = 0, max_len = 1, left, right;
            for (int start = 0; start < len && len - start > max_len / 2;) {
                left = right = start;
                while (right < len - 1 && s[right + 1] == s[right])
                    ++right;
                start = right + 1;
                while (right < len - 1 && left > 0 && s[right + 1] == s[left - 1]) {
                    ++right;
                    --left;
                }
                if (max_len < right - left + 1) {
                    max_left = left;
                    max_len = right - left + 1;
                }
            }
            return s.substr(max_left, max_len);
        }
    };

  • 0
    Z

    could you plz explain:

    while (right < len - 1 && s[right + 1] == s[right])
                    ++right;
    start = right + 1;
    

    and how do you handle odd and even cases in one while loop?

    Thanks!


  • 0

    "abcccccbads"
    say, initially, start =2;
    after executing while loop, you'll have right == 6. Then you set start = right+1 (next one), which is 7, which is the start of next potential palindrome.


  • 7

    In fact, I do not understand why your solution can be faster so much than the dp array method ..... As your method indeed is also to check all the possible palindrome char ....
    The only reason you are so fast I think is because that the test cases contain many many duplicate chars !!!
    You have skipped the duplicate chars to make the beginning searching points very large!!!!


  • 0

    @prime_tang Hi, the start < len in for loop seems not necessary.


  • 0
    S

    @RainbowSecret I think you are right.My algorithm is dp also run O(N*2), but time 147ms.


  • 0

    @prime_tang

    Hi, thanks for sharing your solution. My solution is similar to yours, but it achieved 6ms, slower than yours.
    Then I found your code do early termination with (len - start > max_len / 2), it is really effective. I modified my code and it achieve 3 ms. Thanks your solution again!

    string longestPalindrome(string s) {
            if(s.empty()) return s;
            int max_beg=0, max_end=0;
            int beg=0, end=0;
            for(int i=0; i<s.size() && (s.size()-1-i) > (max_end - max_beg)/2; ++i){
                beg = end = i;
                while(end+1 < s.size() && s[beg] == s[end+1]){
                    end++;
                    i++;
                }
            
                while(beg-1>=0 && end+1<s.size()){
                    if(s[beg-1] != s[end+1]) break;
                    beg--;
                    end++;
                }
                
                if( end-beg > max_end-max_beg){
                    max_beg=beg;
                    max_end=end;
                }
            }
            return s.substr(max_beg, max_end-max_beg+1);
        }
    

  • 0
    F

    @RainbowSecret
    Agree.
    My implementation used two pointers to scan repeated chars, and got AC in 6ms.

    I tried this code, 6ms, same with mine.

    Then I removed the optimization for repeated chars, it went up to 49ms.


  • 0
    S

    @yanchao_hust thx you solution


  • 0
    D

    @prime_tang said in Accepted 4ms c++ solution.:

    start < len && len - start > max_len / 2

    start < len is redundant since len - start > max_len / 2 has said that.


Log in to reply
 

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