My 4ms c++ solution


  • 0
    O

    4ms c++

    string shortestPalindrome(string s) {
    	int n1=s.length();
    	string mystr="$";//2*n1+1
    	int n=2*n1+1;
    	for(auto c : s)
    		mystr+=c, mystr+='$';
    	int* plen=new int[n];
    	int pali_len=1;
    	int i, k, mid=0, l=-1;
    	for(i=0; i<=n/2; i++)
    	{
    		k=0;
    		if(i<l&&2*mid-i>-1)  k=min(plen[2*mid-i], l-i);
    		while(i-k-1>-1&&i+k+1<n&&mystr[i-k-1]==mystr[i+k+1]) k++;
    		plen[i]=k;
    		if(i+k>l) mid=i, l=i+k;
    	}
    	for(i=n/2; i>-1; i--)
    		if(plen[i]==i)  {pali_len=i; break;}
    	string t=s.substr(i);
    	reverse(t.begin(), t.end());
    	return t+s;
    }

  • 0
    M

    can you explain what this mean?
    for(auto c : s)
    mystr+=c, mystr+='$';

    Thanks


  • 0
    O

    if the palindrome's length is an even number,for example, "abccba",the palindrome has no center character. if we change it to "$a$b$c$c$b$a$" the palindrome has the center charater '$'.


Log in to reply
 

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