leetcode 214. Shortest Palindrome

川长思鸟来 2022-08-20 14:23 21阅读 0赞

Given a string S, you are allowed to 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.  
  
  
For example:  
  
  
Given "aacecaaa", return "aaacecaaa".  
  
  
Given "abcd", return "dcbabcd".

class Solution {
    public:
    	string shortestPalindrome(string s) {
    		string str;
    		if (s.empty() || s.length() == 1)
    			return str;
    		if (s.length() == 2)
    		{
    			if (s[0] != s[1])
    				s.insert(s.begin(), s[1]);
    			return s;
    		}
    		if (s.length() == 3)
    		{
    			if (s[0] != s[2])
    			{
    				s.insert(s.begin(), s[1]);
    				s.insert(s.begin(), s[3]);
    			}
    			return s;
    		}
    		int min = 10000;
    		bool f = false;
    		for (int i = s.length() / 2; i > 0; i--)
    		{
    			int k = 0;
    			while (i - k - 1 >= 0 && s[i - k - 1] == s[i + k])
    				k++;
    			if (i - k == 0 && s[i - 1] == s[i])
    			{
    				f = true;
    				string ss = s;
    				string sss(s.begin() + i + k, s.end());
    				if (sss.empty())
    					return s;
    				for (int j = 0; j <= sss.size() / 2; j++)
    				{
    					char aa = sss[j];
    					sss[j] = sss[sss.size() - 1 - j];
    					sss[sss.size() - 1 - j] = aa;
    				}
    				ss.insert(0, sss.c_str());
    				if (ss.length() < min)
    				{
    					min = ss.length();
    					str = ss;
    				}
    			}
    			k = 1;
    			while (i - k >= 0 && i + k < s.length() && s[i - k] == s[i + k])
    				k++;
    			if (i - k == -1 && s[i - 1] == s[i + 1])
    			{
    				f = true;
    				string ss = s;
    				string sss(s.begin() + i + k, s.end());
    				if (sss.empty())
    					return s;
    				for (int j = 0; j <= sss.size() / 2; j++)
    				{
    					char aa = sss[j];
    					sss[j] = sss[sss.size() - 1 - j];
    					sss[sss.size() - 1 - j] = aa;
    				}
    				ss.insert(0, sss.c_str());
    				if (ss.length() < min)
    				{
    					min = ss.length();
    					str = ss;
    				}
    			}
    			if (f)
    				return str;
    		}
    		string ss = s;
    		string sss(s.begin() + 1, s.end());
    		for (int j = 0; j <= sss.size() / 2; j++)
    		{
    			char aa = sss[j];
    			sss[j] = sss[sss.size() - 1 - j];
    			sss[sss.size() - 1 - j] = aa;
    		}
    		ss.insert(0, sss.c_str());
    		return ss;
    	}
    };