s4553711
7/13/2017 - 2:56 PM

5.cpp

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() == 0) return s;
        size_t max_len = 0;
        std::pair<size_t, size_t> res;
        for(size_t i = 0; i < s.size(); ++i) {
            for(size_t j = 1; j <= i && i + j  < s.size() ; ++j) {
                //cout << "odd: i:" << i << ", j:" << j << ", max: " << max_len << endl;
                //cout << "comp: " << (i-j) << " vs " << (i+j) << endl;                
                if (s[i-j] == s[i+j]) {
                    if (2 * j + 1 > max_len) {
                        max_len = 2 * j + 1;
                        res = std::make_pair(i, j);
                    }
                } else {
                    break;
                }
            }
            for (size_t j = 1; j <= i && i + j - 1 < s.size(); ++j) {
                //cout << "even: i:" << i << ", j:" << j << ", max: " << max_len << endl;
                //cout << "comp: " << (i-j) << " vs " << (i+j-1) << endl;
                if (s[i-j] == s[i+j-1]) {
                    if (2 * j > max_len) {
                        max_len = 2 * j;
                        res = std::make_pair(i, j);
                    }
                } else  {
                    break;
                }
            }
            //cout << "----" << endl;
        }
        //cout << "max_len: " << max_len << endl;
        return max_len != 0 ? s.substr(res.first - res.second, max_len) : s.substr(0, 1);
    }
};