C++ 4ms Manacher


  • 0
    N
    class Solution {
    public:
    	string shortestPalindrome(string s) {
    	    if(s == "") return s;
    		string scopy(s.begin()+1,s.end());
    		reverse(scopy.begin(), scopy.end());
    		string ans = scopy + s;
    		int len = s.size(), i = 0, j, k;
    		while (i < len){
    			string tmp = scopy;
    			int r = i;
    			while (r < len && s[r] == s[r + 1]) ++r;
    			j = i - 1; k = r + 1;
    			while (j >= 0 && k < len && s[j] == s[k]){
    				--j;
    				++k;
    			}
    			if (j == -1 && k == len){
    				return s;
    			}
    			else if(j == -1 && k != len){
    				tmp = s.substr(k, len -  k + 1);
    				reverse(tmp.begin(), tmp.end());
    				tmp += s;
    				ans = ans.size() > tmp.size() ? tmp : ans;
    			}
    			i = r + 1;
    		}
    		return ans;
    	}
    };

  • -1

Log in to reply
 

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