Simple C++ O(1) space && O(n) time solution, without any "tricks"


  • 3
    J

    For the Interview it is good to demonstrate that you can use regex or standard functions to remove all unnecessary symbols, but, I believe, eventually interviewer will want you to write something like this.
    This is "two pointers" solution without any modifications of the original string and I think quite straightforward.

    bool isPalindrome(string s) {

    int r = s.length();
    if(r==0) return true;
    
    int l=0;
    r--;
    
    while(l<=r){
        if(!('a' <= s[l] && s[l] <= 'z') && !('A' <= s[l] && s[l] <= 'Z') && !('0' <= s[l] && s[l] <= '9')){
            l++; continue;
        }
        if(!('a' <= s[r] && s[r] <= 'z') && !('A' <= s[r] && s[r] <= 'Z') && !('0' <= s[r] && s[r] <= '9')){
            r--; continue;
        }
        
        if(s[l] != s[r] && s[l]+32 != s[r] && s[l]-32 != s[r]) return false;
        
        l++;
        r--;
    }
    
    return true;
    

    }


  • 0
    H

    How much time does this take? I wrote a similar solution but it takes 88ms to solve all cases, whereas according to the solution time graphs, people have solved it even faster than this implementation. What are those implementations? Any clue? Here's a screenshot http://i.imgur.com/lGQc2oW.png?1


  • 1
    T

    How about the case s=0P ?

    '0'+32 = 'P', but s is not palindrome.


  • 0
    J

    Sorry for late reply, I just ran my latest submission, and it took 16 ms, when I ran it the time when it was first time accepted, that time it took 56 ms. As far as I can see test running time depends on many factors like home many users currently testing their solutions simultaniously and so on...in many discusions you can feel the same reading between the lines.


Log in to reply
 

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