Palindrome问题

Palindrome问题的分类

• 第一类问题的套路是给定一个string or char array, 可以把每一个unit单独拆出来进行拼装。问你用这里面的char（不一定全用，根据题目条件而定）能不能组成palindrome或者能够组成的最长的palindrome的长度。

  • 如果是必须全用，那么判断条件就是至多有不超过一个char's freq是odd
  • 如果可以不全用，那么就变成取所有的偶数freq的char和奇数freq - 1的char，再加最多一个odd的char, 这种问题就是HashMap统计frequency的典型应用。一般时间复杂度就是O(n)。

• 第二类问题问的是返回所有可以组成的palindrome。

  • 第一种考法是permutation问题，这里组成的palindrome顺序matters而且要返回所有结果。不过要确保我们可以组成palindrome, 第一类问题的验证往往也会被用到。之后问题就变成了在half chars里面做dfs permutation with duplicates。不过这里头有个edge case, 那就是中间有没有落单的那个char, 如果有就要加进去。这种题目的时间复杂度一般是指数级别。
  • 第二种考法是combination问题，也就是给定string，求所有的palindrome划分，具体可见palindrome partitioning。

• 第三类问题问的是求满足条件的substring palindrome，比如找最长的substring palindrome, 这种问题的核心是substring, 所以暴力解的复杂度也就是O(n^3)的（O(n^2)枚举起点和终点。 然后判断是不是palindrome还需要O(n)）。但是通过使用中心扩散法，我们可以比单纯的枚举起点和终点要节省时间。这种问题的时间复杂度一般是O(n^2)。

• 第四类问题，那就是验证一个给定的input是不是palindrome，这个模版同时也是reverse array/anything的模板

  • LinkedList：因为只能单向遍历，所以我们只能取中点，然后reverse后半段。最后比较相同。
  • Integer。因为是signed number，所以我们可以直接做乘除的运算。
  • Bits。因为是unsigned number，所以我们不能直接进行乘除的运算，而是要使用bitwise shift

题目

第一类：HashMap统计count

• Leetcode 409. Longest Palindrome
• Longest Palindrome by Shuffling or Removing
• Leetcode 266. Palindrome Permutation

第二类：DFS找permutation or combination

• Leetcode 267. Palindrome Permutation II （这道题其实是第一类＋第二类，因为先得判断在所有char全用的情况下能不能形成palindrome）
• Leetcode 131. Palindrome Partitioning
• Leetcode 132. Palindrome Partitioning II (这道题还考察了区间DP)
• Leetcode 247. Strobogrammatic Number II (这道题和palindrome permutation的区别在于尽管都是permutation去组合新的string，palindrome permutation给定的备选的array里头已经包含了duplicate，所以我们要使用permutation in array with duplicate的做法。而这道题给定的备选array都是distinct element，但是我们是可以取duplicate的，所以这里相对来说更容易，我们甚至都不需要visited array，每层遍历的时候随便取就好了)
• Leetcode 248. Strobogrammatic Number III

第三类：中心扩散法

• Leetcode 5. Longest Palindromic Substring
• Leetcode 336. Palindrome Pairs
• Leetcode 214. Shortest Palindrome

第四类：panlindrome validation

• Leetcode 234. Palindrome Linked List
• Leetcode 9. Palindrome Number
• Leetcode 125. Valid Palindrome
• Leetcode 246. Strobogrammatic Number