Brute force method with Hashtable: 20ms


  • 0
    Y
    class Solution {
    public:
        string shortestPalindrome(string s) {
            
            unordered_map<char, int> vmap;
            for(auto x: s)
                vmap[x] ++;
            
            int ne = 0;
            for(auto& x: vmap)
            {
                if(x.second % 2 != 0)
                    ne ++;
            }
            
            int n = s.length() - 1;
            if(n < 0)
                return s;
            const char* sc = s.c_str();
            
            while(n >= 0)
            {
                if(ne <= 1)
                {
                    
                    int st = 0, ed = n;
                    while(st < ed && sc[st] == sc[ed])
                    {
                        st ++;
                        ed --;
                    }
                    
                    if(st >= ed)
                    {
                        string s1 = s.substr(n + 1, s.length() - n - 1);
                        reverse(s1.begin(), s1.end());
                        return s1 + s;
                    }
                }
                
                vmap[sc[n]] --;
                if(vmap[sc[n]] % 2 == 0)
                    ne --;
                else
                    ne ++;
                    
                n --;
                
            }
            
            return s;
        }
    };
    

Log in to reply
 

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