LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 判断一个字符串是否为回文串的方法是，从中心字符出发，往两边扩展依次检查。回文串的长度可以为奇数或者偶数，需要根据长度来分别处理两种情况，如果为奇数，则中间是单个字符，如果为偶数，则中间是两个字符
• 为了统一长度为奇数和偶数的两种情况，一个做法是扩展原来的字符串，在字符两侧插入一个特殊字符，这样原来偶数长度的字符中间也是单个字符

s = abba => str = #a#b#b#a#

#a#b#b#a#
012345678

// 均可以从单个字符出发向两边扩展
0 # => #
1 a => #a#
2 # => #
3 b => #b#
4 # => b#b => #b#b# => a#b#b#a => #a#b#b#a#
5 b => #b#
6 # => #
7 a => #a#
8 # => #

• 中心扩展算法对每个字符往两边扩展依次检查，最后取最大长度的回文子串即可，时间复杂度为 O(n ^ 2)

class Solution {
 public:
  string longestPalindrome(string s) {
    string str{'#'};
    for (auto& x : s) {
      str += x;
      str += '#';
    }  // str为扩展后的字符串
    string res;
    int len = 0;
    for (int i = 0; i < size(str); ++i) {
      int l = i;
      int r = i;
      while (str[l] == str[r]) {
        --l;
        ++r;
        if (l < 0 || r >= size(str)) {
          break;
        }
      }
      if (r - l > len) {
        len = r - l;
        res = str.substr(l + 1, r - l - 1);
      }
    }
    res.erase(remove(begin(res), end(res), '#'), end(res));
    return res;
  }
};

• 1975 年，Manachar 提出了时间优化到 O(n) 的 Manachar 算法
• 对于上述例子，引入一个数组 p[i] 表示 i 位置的最大回文半径（左侧到中心的长度，比如回文串长度为 5，则半径为 3），p[i] - 1 就是原来的回文子串长度（(回文半径 - 1) * 2 + 1 = 原回文串长度 * 2 + 1）

#a#b#b#a#
012345678

i    = 0 1 2 3 4 5 6 7 8
p[i] = 1 2 1 2 5 2 1 2 1
// 可以发现 p[i] - 1 就是原来的回文子串长度，最大回文子串长度就是 5 - 1 = 4

• 于是求最大回文子串就可以转化为求该字符串对应的数组
• Manacher 算法的优化点在于，对于 p[i]，其之前的 p[j] (j < i) 已经求过了，而 p[i] 可以用 p[j] 算出，从而只需要一次遍历，使得复杂度为 O(n)
• p[j] 的右边界为 j + p[j]，将最大的右边界记为mx，mx 对应的 j 记为 id，这个右边界只会不断右移而不会回退

#a#b#b#a#
012345678

i    = 0 1 2 3 4 5 6 7 8
p[i] = 1 2 1 2 5 2 1 2 1
mx   = 1 3 3 5 9 7 7 9 9

• 现在计算 p[i]，i 的位置有两种情况，一是与右边界相等，二是在右边界内（又分为三种情况）
• 先考虑 i 在右边界内的情况。考虑 i 关于 id 的对称点 j

// i < mx
__________id__________mx
__j_______id_______i__mx  // j 为 i 关于 id 的对称点，j = id - (i - id) = 2 * id - i

• 因为 p[j] 已经计算过，根据 p[j] 的情况来考虑 p[i]，此时有三种情况
• 第一种情况：j 的左边界超出了 id 的左边界

// if (i < mx && p[j] > mx - i) p[i] = mx - i;
 ___________id___________mx
---j---_____id________i__mx  // 必定 p[i] = mx - i

// 如果 p[i] 右边界超出 mx 的话，即 p[i] > mx - i
---j---_____id_____---i---mx  // id 的右边界应该超出 mx，与 mx 是最大右边界的前提矛盾

• 第二种情况：j 的左边界小于 id 的左边界

// if (i < mx && p[j] < mx - i) p[i] = p[j];
___________id___________mx
_-j-_______id________i__mx  // 必定p[i] = p[j]

• 第三种情况：j 的左边界与 id 的左边界重合

// if (i < mx && p[j] == mx - i) p[i] = p[j]; // 仍可能增加
___________id___________mx
--j--______id________i__mx  // p[i] >= p[j] 或 mx - i，p[i] 可以继续增加，还需要向两边扩展计算 p[i]

• 综上，i 在右边界内时，p[i] 的计算如下

if (i < mx) {
  if (p[2 * id - i] < mx - i) {
    p[i] = p[2 * id - i];
  }
  if (p[2 * id - i] > mx - i) {
    p[i] = mx - i;
  }
  if (p[2 * id - i] == mx - i) {
    p[i] = mx - i;
    while (str[i - p[i]] == str[i + p[i]]) {
      ++p[i];
    }
  }
}

• 接着考虑 i 与右边界相等的情况，即 i 抵达了右边界的位置，此时向两边扩展计算 p[i] 即可

if (i == mx) {
  p[i] = 1;
  while (i >= p[i] && str[i - p[i]] == str[i + p[i]]) {
    ++p[i];
  }
}

• 合并上述两种情况

if (i < mx) {
  if (p[2 * id - i] < mx - i) {
    p[i] = p[2 * id - i];
  }
  if (p[2 * id - i] > mx - i) {
    p[i] = mx - i;
  }
  if (p[2 * id - i] == mx - i) {
    p[i] = mx - i;
    while (i >= p[i] &&  // 确保 i - p[i] >= 0 防越界
           str[i - p[i]] == str[i + p[i]]) {
      ++p[i];
    }
  }
} else if (i == mx) {
  p[i] = 1;
  while (i >= p[i] && str[i - p[i]] == str[i + p[i]]) {
    ++p[i];
  }
}

• 合并逻辑流可以简化为

if (i < mx) {
  p[i] = min(p[2 * id - i], mx - i);
} else if (i == mx) {
  p[i] = 1;
}
while (i >= p[i] && str[i - p[i]] == str[i + p[i]]) {
  ++p[i];
}

• 每次计算出 p[i] 后，与右边界比较，如果超出当前最大右边界，则将最大右边界更新为 i 的右边界

if (mx < i + p[i]) {
  id = i;
  mx = i + p[i];
}

• 解法如下

class Solution {
 public:
  string longestPalindrome(string s) {
    if (size(s) <= 1) {
      return s;
    }
    string str{"#"};
    for (auto& x : s) {
      str += x;
      str += '#';
    }  // str为扩展后的字符串
    int sz = size(str);
    vector<int> p(sz);
    int start = 0;   // 最长回文子串首字符在原字符串中的下标
    int maxLen = 0;  // 最长回文子串的长度

    int id = 0;
    int mx = 0;  // 最大右边界 = p[id] + id

    for (int i = 0; i < sz; ++i) {
      if (i < mx) {
        p[i] = min(p[2 * id - i], mx - i);
      } else if (i == mx) {
        p[i] = 1;
      }
      while (i >= p[i] && str[i - p[i]] == str[i + p[i]]) {
        ++p[i];
      }
      if (mx < i + p[i]) {  // 检查是否超出右边界
        id = i;
        mx = i + p[i];
      }
      if (p[i] - 1 > maxLen) {  // p[i] - 1 是回文子串的长度
        start = i;
        maxLen = p[i] - 1;
      }
    }
    return s.substr((start - p[start] + 1) / 2, maxLen);
  }
};