文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給定一個字符串 s，你可以通過在字符串前面添加字符將其轉換為回文串。
找到并返回可以用這種方式轉換的最短回文串。

示例 1: 輸入: "aacecaaa" 輸出: "aaacecaaa"示例 2: 輸入: "abcd" 輸出: "dcbabcd"

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/shortest-palindrome
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 參考官方題解，字符串哈希
• 使用字符串哈希，對s的頭部子串的正序哈希和逆序哈希進行計算，找出最長相等的回文串子串，其結束位置為 idx
• 剩余的部分為 [idx+1, n)，將其反轉后加到 s 頭部就是最短的新回文串

class Solution { public:string shortestPalindrome(string s) {long long n = s.size(), i, idx = -1, base = 1, mod = 1e9+7;long long left = 0, right = 0;for(i = 0; i < n; i++) {left = (left*131 + s[i])%mod;right = (right + s[i]*base)%mod;if(left == right)idx = i;base *= 131;base %= mod;}string A = s.substr(idx+1);reverse(A.begin(), A.end());return A+s;} };

0 ms 7.3 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 214. 最短回文串（字符串哈希）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。