One AC c++ implementation


  • 0

    This problem is really easy, but I do not get AC for one implementation, the bug I meet is that the loop in the while(left<right),

    I just use like this

     while(!check(s[left])) left++;
    

    But as we can expect if we think carefully, the left might cause RE, because we do not check the left is a valid index.

    So to fix this bug, we should write like this:

    while(left<len && !check(s[left])) left++;
    

    Besides, we can use

      isalnum(c) to check whether c is a valid char.
      to_lower  to change the 'A' to 'a'
      OR to_upper similarly.
    

    Here is the final code implementation.

      class Solution {
        public:
            bool isPalindrome(string s) {
                int len=s.size();
                if(len<=1)  return true;
                int left=0, right=len-1;
                while(left<right){
                    while(left<=len-1 && !check(s[left])) left++;
                    while(right>=0 && !check(s[right])) right--;
                    if(left==len || right==-1)  return true;
                    if(toupper(s[left])!=toupper(s[right]))  return false;
                    left++;
                    right--;
                }
                return true;
            }
            
            bool check(char c){
                return (c>='a' && c<='z') || (c>='A' && c<='Z') || (c>='0' && c<='9');
            }
        };

  • 0
    Y

    You don't need the first two line in the function, since if the length is 0 or 1, left will be greater than or equal to right, it will still return true.

    Also, if you change the condition of the 2 while loops inside the inner loop to while (left < right && ...) and while (left < right && ...), then you don't need the check for the left and right bound. This won't gain improvement to the runtime but it might look better. Also, when you call the toupper() function, you can first check if left < right, if left is equal to right, then you don't need 2 extra function calls.


  • 0

    Thanks for your advice!


Log in to reply
 

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