3ms simple C++ solution without using KMP


  • 0
    O

    The idea is very simple: if a string is palindrome its sums of left part and right part must be the same

    class Solution {
    public:
    string shortestPalindrome(string s) {
    unsigned long long leftSum = 0, rightSum = 0;
    int slength = s.size();
    for (int i=0; i<slength/2; i++) {
    leftSum += s[i];
    rightSum += s[slength - 1 - i];
    }
    int count = slength;
    while (count > 0) {
    if (leftSum == rightSum) {
    if (isPalindrome(s,count)) {
    break;
    }
    }
    if (count % 2 == 0) {
    leftSum -= s[count /2-1];
    rightSum -= s[count-1];
    }
    else {
    rightSum -= s[count-1];
    rightSum += s[count /2];
    }
    count --;
    }
    string addStr = "";
    for (int i=0; i<slength - count; i++) {
    addStr += s[slength - 1 - i];
    }
    return addStr + s;
    }
    bool isPalindrome(const string & s, int count){
    int l = 0, r = count-1;
    while (s[l] == s[r] && r> l){l++;r--;};
    return l >= r;
    }
    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.