leetcode 214. Shortest Palindrome | 214. 最短回文串（Java）

https://leetcode.com/problems/shortest-palindrome/

看了 Related Topics - Rolling Hash 下的相关题目，看到了：187. Repeated DNA Sequences 这道题，想到了如下解法。一开始用了个 set 存储可能的匹配，在一个测试用例上 OOM 了，后来发现不需要 set。

因为回文串包含两种情况，一种是奇数回文，一种是偶数回文，导致边界一直没处理好，所以后来干脆分类讨论了。

做完之后看了答案，看来不需要分类讨论。

另外，本题解的时间复杂度是 O(n^2)，因为字符串比较的复杂度是线性的（对于相同的字符串来说，虽然常量池只存一遍，但运行时创建的字符串是在堆中的，所以并没有通过比较在常量池中的引用地址来判断是否相等，而且 equals 方法点进去之后，可以看到是逐个字符比较的。）

想要 O(n) 的话，可以用 KMP，详见官方答案吧。

class Solution {
    public String shortestPalindrome(String s) {
        int L = s.length();
        if (L <= 1) return s;
        
        String result = null;
        // 以字母本身为轴
        for (int i = L / 2; i >= 0; i--) {
            if (2 * i + 1 > L) continue;
            String right = s.substring(i + 1, 2 * i + 1);
            String left = new StringBuilder(s.substring(0, i)).reverse().toString();
            if (left.equals(right)) {
                result = new StringBuilder(s.substring(i + 1)).reverse() + s.substring(i);
                break;
            }
        }
        // 以字母本身为右回文串的首字母
        for (int i = (L + 1) / 2; i >= 0; i--) {
            if (2 * i > L) continue;
            String right = s.substring(i, 2 * i);
            String left = new StringBuilder(s.substring(0, i)).reverse().toString();
            if (left.equals(right)) {
                String newResult = new StringBuilder(s.substring(i)).reverse() + s.substring(i);
                if (result == null || newResult.length() < result.length()) result = newResult;
                break;
            }
        }
        return result;
    }
}