Leetcode：超出时间限制，最长回文子串

Question

我正在尝试解决 LeetCode 问题 5. Longest palindromic substring:

Given a string s, return the longest palindromic substring in s.

我收到超长字符串（最多 1000 个字符）的时间限制，但另一方面，在我的终端上使用相同的长字符串会立即给出正确答案。这是我收到错误的字符串：

"zudfweormatjycujjirzjpyrmaxurectxrtqedmmgergwdvjmjtstdhcihacqnothgttgqfywcpgnuvwglvfiuxteopoyizgehkwuvvkqxbnufkcbodlhdmbqyghkojrgokpwdhtdrwmvdegwycecrgjvuexlguayzcammupgeskrvpthrmwqaqsdcgycdupykppiyhwzwcplivjnnvwhqkkxildtyjltklcokcrgqnnwzzeuqioyahqpuskkpbxhvzvqyhlegmoviogzwuiqahiouhnecjwysmtarjjdjqdrkljawzasriouuiqkcwwqsxifbndjmyprdozhwaoibpqrthpcjphgsfbeqrqqoqiqqdicvybzxhklehzzapbvcyleljawowluqgxxwlrymzojshlwkmzwpixgfjljkmwdtjeabgyrpbqyyykmoaqdambpkyyvukalbrzoyoufjqeftniddsfqnilxlplselqatdgjziphvrbokofvuerpsvqmzakbyzxtxvyanvjpfyvyiivqusfrsufjanmfibgrkwtiuoykiavpbqeyfsuteuxxjiyxvlvgmehycdvxdorpepmsinvmyzeqeiikajopqedyopirmhymozernxzaueljjrhcsofwyddkpnvcvzixdjknikyhzmstvbducjcoyoeoaqruuewclzqqqxzpgykrkygxnmlsrjudoaejxkipkgmcoqtxhelvsizgdwdyjwuumazxfstoaxeqqxoqezakdqjwpkrbldpcbbxexquqrznavcrprnydufsidakvrpuzgfisdxreldbqfizngtrilnbqboxwmwienlkmmiuifrvytukcqcpeqdwwucymgvyrektsnfijdcdoawbcwkkjkqwzffnuqituihjaklvthulmcjrhqcyzvekzqlxgddjoir"

您可以在下面找到我提交的代码。我想知道如何优化我的代码（或者如果它不好的话可能重新开始）。代码的基本思想是，我使用滑动 window 技术在每次迭代时创建一个子字符串，并使用辅助方法检查该子字符串是否为回文。在运行时开始时，我的 window 等于字符串的大小，并且随着每次迭代逐渐变小。一旦找到回文子串，它就会 return 子串。

示例：

如果我的字符串是“babad”。第一个子字符串将是整个字符串 (babad)。显然，它不是回文，所以通过减少右边的 window 我可以重新检查字符串是否是回文。在第二次迭代中，window 现在是字符串大小 - 1，这给了我们两个子字符串（baba 和 abad），这两个子字符串都不是回文，因此它会继续，直到它偶然发现一个回文子字符串。我的第一个提交是使用双 for 循环的天真的暴力破解，这给了我 O(n^2) 的复杂性，但我真的不明白为什么这个新版本会很慢的问题。

感谢任何帮助。

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

该算法从外向内工作会浪费大量时间。意识到回文有一个“中心”（在相邻索引上或之间），并且您的算法通常会使用相同中心但尺寸减小来寻找回文。您可以通过从内向外工作来减少工作，即 select 所有可能的中心，并查看具有该中心的最大回文是什么。这样您每个中心只会进行一次扫描。因此，遍历所有可能的中心（on 索引和 between 两个索引），看看哪个是您可以通过这种方式找到的最大回文.

然后您可以进一步优化，方法是从弦中间的中心开始（因为它们可能提供最大的弦），然后将您的中心“散开”远离弦的中间，直到你离字符串的外端太近，使得不可能改进你已经找到的最长回文。

最后，避免创建新的字符串，只使用索引（左、右、...等），只有在你已经确定了字符串时才真正创建一个字符串start/end最大回文的索引。

Leetcode：超出时间限制，最长回文子串

Leetcode: Time limit exceeded, Longest palindromic substring

c++

string

algorithm

c++17

sliding-window