Leetcode:超过时间限制，最长回文子字符串

Question

我想知道如何优化LeetCode问题：5.最长回文子串的解决方案

给定一个字符串s，返回s中最长的回文子字符串。

对于非常长的字符串(最多1000个字符)，我的时间限制超过了，但是另一方面，在我的终端上使用相同的长字符串会立即给出正确的答案。下面是我得到错误的字符串：

"zudfweormatjycujjirzjpyrmaxurectxrtqedmmgergwdvjmjtstdhcihacqnothgttgqfywcpgnuvwglvfiuxteopoyizgehkwuvvkqxbnufkcbodlhdmbqyghkojrgokpwdhtdrwmvdegwycecrgjvuexlguayzcammupgeskrvpthrmwqaqsdcgycdupykppiyhwzwcplivjnnvwhqkkxildtyjltklcokcrgqnnwzzeuqioyahqpuskkpbxhvzvqyhlegmoviogzwuiqahiouhnecjwysmtarjjdjqdrkljawzasriouuiqkcwwqsxifbndjmyprdozhwaoibpqrthpcjphgsfbeqrqqoqiqqdicvybzxhklehzzapbvcyleljawowluqgxxwlrymzojshlwkmzwpixgfjljkmwdtjeabgyrpbqyyykmoaqdambpkyyvukalbrzoyoufjqeftniddsfqnilxlplselqatdgjziphvrbokofvuerpsvqmzakbyzxtxvyanvjpfyvyiivqusfrsufjanmfibgrkwtiuoykiavpbqeyfsuteuxxjiyxvlvgmehycdvxdorpepmsinvmyzeqeiikajopqedyopirmhymozernxzaueljjrhcsofwyddkpnvcvzixdjknikyhzmstvbducjcoyoeoaqruuewclzqqqxzpgykrkygxnmlsrjudoaejxkipkgmcoqtxhelvsizgdwdyjwuumazxfstoaxeqqxoqezakdqjwpkrbldpcbbxexquqrznavcrprnydufsidakvrpuzgfisdxreldbqfizngtrilnbqboxwmwienlkmmiuifrvytukcqcpeqdwwucymgvyrektsnfijdcdoawbcwkkjkqwzffnuqituihjaklvthulmcjrhqcyzvekzqlxgddjoir"

下面您可以找到我使用两个函数的问题的解决方案。

1. 检查wheather给定的字符串是回文。
2. 长回文()：使用滑动窗口检查wheather的算法是最长的回文。

class Solution {
public:
  bool ispalindrome(string s) {
    int i = 0, j = s.size() - 1;
    while(i <= j){
      if(s[i] != s[j]){
        return false;
      }
      i++;
      j--;
    }
    return true;
  }
  string longestPalindrome(string s) {
    int window_size = s.size() - 1;
    int left = 0, right = window_size;
    string tmp_str = "";
    while (right < s.size()) {
      tmp_str.append(s.begin() + left, s.begin() + right + 1);
      if (ispalindrome(tmp_str)) {
        return tmp_str;
      }
      if((right + 1) < s.size()) {
        tmp_str = "";
        right++;
        left++;
      } else {
        tmp_str = "";
        window_size--;
        right = window_size;
        left = 0;
      }
    }
    return s;
  }
};

Answer 1

该算法从内向外工作，损失了大量的时间。要意识到回文有一个“中心”(在相邻索引之间)，您的算法通常会使用相同的中心查找回文，但大小会越来越小。您可以通过从内到外工作来减少工作量，即选择所有可能的中心，然后看看有这个中心的最大回文是什么。这样，每个中心只能进行一次扫描。因此，遍历所有可能的中心(包括索引，以及两个索引之间)，看看哪个是您可以找到的最大回文。

然后，您可以进一步优化，方法是从字符串中间的中心开始(因为它们可能提供最大的字符串)，然后将中心从字符串的中间“扇”开，直到您太接近字符串的外部端，这样就不可能改进您已经找到的最长回文。

最后，避免创建新字符串，只使用索引(左、右、...etc)，只有在已经确定了最大回文的起始/结束索引时才真正创建字符串。