Leetcode: 【每日一题】- 2019-10-22 - 214. 最短回文串

[azl397985856]

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

示例 1:

输入: "aacecaaa"
输出: "aaacecaaa"
示例 2:

输入: "abcd"
输出: "dcbabcd"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-palindrome
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[maninbule]

领取

思路：把给定的字符串的正序s1和反序s2都分别初始化出哈希数组h1,h2来，然后进行区间比较，h1[i,len]与h2[1,len-i+1],若两区间哈希值相同，就直接返回s2.substr(0,i-1)+s1即可

其实没啥思路，我就是套了一个字符串哈希的模板hh。不过这时间不忍直视

typedef unsigned long long ull;
const int Pr = 131;
const int maxn = 1e6+10;
class Solution {
public:
    int len; string s1,s2;
    ull h1[maxn],h2[maxn],p[maxn];

    ull get(int l,int r,ull h[]){
        return h[r]-h[l-1]*p[r-l+1];
    }
    void init(){
        p[0] = 1;
        for(ull i =  1;i<=len;i++){
            p[i] = p[i-1]*Pr;
            h1[i] = h1[i-1]*Pr + s1[i-1];
            h2[i] = h2[i-1]*Pr + s2[i-1];
        }
    }    
    string shortestPalindrome(string s) {
        len = s.length(),s1 =s,s2 = s;
        reverse(s2.begin(),s2.end());
        init();
        for(int i = 1;i<=len;i++){
            if(get(i,len,h2) == get(1,len-i+1,h1)){
                return s2.substr(0,i-1)+s1;
            }
        }
        return "";
    }
};

[azl397985856]

@maninbule done

[maninbule]

把大数组换成了可变长数组vector，速度有所提升。

typedef unsigned long long ull;
const int Pr = 131;
class Solution {
public:
    int len; string s1,s2;

    ull get(int l,int r,vector<ull> &h,vector<ull> &p){
        return h[r]-h[l-1]*p[r-l+1];
    }
    void init(vector<ull> &p,vector<ull> &h1,vector<ull> &h2){
        p[0] = 1;
        for(ull i =  1;i<=len;i++){
            p[i] = p[i-1]*Pr;
            h1[i] = h1[i-1]*Pr + s1[i-1];
            h2[i] = h2[i-1]*Pr + s2[i-1];
        }
    }    
    string shortestPalindrome(string s) {
        len = s.length(),s1 =s,s2 = s;
        reverse(s2.begin(),s2.end());
        vector<ull> h1(len+10),h2(len+10),p(len+10);
        init(p,h1,h2);
        for(int i = 1;i<=len;i++){
            if(get(i,len,h2,p) == get(1,len-i+1,h1,p)){
                return s2.substr(0,i-1)+s1;
            }
        }
        return "";
    }
};