214. Shortest Palindrome

Given a string s, you can convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

Example 1:

Input: s = "aacecaaa"
Output: "aaacecaaa"
Example 2:

Input: s = "abcd"
Output: "dcbabcd"

Constraints:

0 <= s.length <= 5 * 104
s consists of lowercase English letters only.

// brute force
class Solution {
public:
    string shortestPalindrome(string s) {
        string r(s.rbegin(), s.rend());
        int length = s.size();
        for (int i=0; i<length; ++i) {
            if (s.compare(0, length-i, r, i, length-i) == 0) {
                return r+s.substr(length-i, i);
            }
            // cout << i << endl;
        }
        return "";
    }
};

Runtime: 12 ms, faster than 28.67% of C++ online submissions for Shortest Palindrome.
Memory Usage: 7.4 MB, less than 9.70% of C++ online submissions for Shortest Palindrome.

https://www.geeksforgeeks.org/reverse-a-string-in-c-cpp-different-methods/

https://www.cnblogs.com/grandyang/p/4523624.html

https://www.youtube.com/watch?v=GTJr8OvyEVQ

https://www.cnblogs.com/grandyang/p/6992403.html

class Solution {
public:
    string shortestPalindrome(string s) {
        string r(s.rbegin(), s.rend());
        int length = s.size();
        vector<int> next = BuildNext(s, length);
        
        int i = 0, j = 0;
        while (i < length) {
            if (r[i] == s[j]) {
                //match
                ++i;
                ++j;
            }
            else if (j == 0) {
                ++i;
            }
            else {
                j = next[j];
            }
        }
        
        return r + s.substr(j, length-j);
    }
    
    vector<int> BuildNext(const string& s, const int& length) {
        vector<int> next(length, 0);
        int i = 1, j = 0;
        while (i < length-1) {
            if (s[i] == s[j]) {
                // match
                ++i;
                ++j;
                next[i] = j;
            }
            else if (j == 0) {
                ++i;
            }
            else {
                j = next[j];
            }
        }
     
        return next;
    }
};

Runtime: 4 ms, faster than 94.27% of C++ online submissions for Shortest Palindrome.
Memory Usage: 7.6 MB, less than 9.70% of C++ online submissions for Shortest Palindrome.

KMP 算法：

• 第一步：建立next库
  • init pattern长度的vector=0
  • j=0, i=1 左指针，右指针
  • while i<length-1 （最后一位不用考虑）
    • if match
      • next[i+1] = j+1; 因为i+1是对应了next里面的位置，如果当前mismatch需要回到的pattern的index，j+1是因为j th已经match了，所以只需要从j+1的pattern开始和原始string对比match
      • ++i; ++j;
    • if not match
      • if j ==0 ~> ++i（默认next[i+1] = 0）
      • if j != 0 ~> j = next[j]
• 第二步：匹配r和s， r作为原始string，s作为pattern，匹配到r匹配完毕为止
  • i=0是r的index， j=0是s的index
  • while i<length
    • if match
      • ++i; ++j; 不需要更新next
    • if not match 类似上面的逻辑
      • if j ==0 ~> ++i（默认next[i+1] = 0）
      • if j != 0 ~> j = next[j]
• 最后输出的时候，r全部输出，附加jth 的s以及后面的整个string。不用j+1th是因为最后一步的match肯定成立，r[-1]肯定等于s[0]， 所以++j已经把j右移到不确定匹配与否的index上了。