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

深藏阁楼爱情的钟 2022-09-13 11:21 119阅读 0赞

## 题目 ##

[https://leetcode.com/problems/shortest-palindrome/][https_leetcode.com_problems_shortest-palindrome]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

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

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

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

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

想要 O(n) 的话，可以用 KMP，详见官方答案吧。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

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;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]

[https_leetcode.com_problems_shortest-palindrome]: https://leetcode.com/problems/shortest-palindrome/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/60bb602616e04ad482d33f8672b48c36.png
[187. Repeated DNA Sequences]: https://leetcode.com/problems/repeated-dna-sequences/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/e2d7fd19dc5e4e9d8699f65704e6b383.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/d4c62b53d3994bea974e15d8c5ec84c1.png