TLE when running the super long test case


  • 0
    W

    I got time limit exceeded error when running this test case Last executed input: "A man, a plan, a cameo, Zena, Bird, Mocha, Prowel, a rave, Uganda, Wait, a lobola, ..." Sorry for not posting the entire string as it is super long.

    I have two pointers: one starting at 0 and one starting at length-1. Whenever I see a non-alphanumeric character I skip to the next character. This is similar to one of the solutions posted where it first removes all non-alphanumeric characters. I understand it is good solution; what I don't understand is why my code would get TLE error because it seems my code is doing basically the same thing. THANKS

    public class Solution {
    public boolean isPalindrome(String s) {
        if(s.length()==0){return true;}
        char[] chars = s.toCharArray();
        int i=0;
        int j=chars.length-1;
        while(j>=i){
            String iChar=String.valueOf(chars[i]);
            String jChar=String.valueOf(chars[j]);
            if(!iChar.matches("[A-Za-z0-9]")||!jChar.matches("[A-Za-z0-9]")){
                if(!iChar.matches("[A-Za-z0-9]")){i++;}
                if(!jChar.matches("[A-Za-z0-9]")){j--;}
            }
            else{
                if(!iChar.toLowerCase().equals(jChar.toLowerCase())){
                    return false;
                }
                i++;
                j--;
            }
        }
        return true;
    }

  • 2
    Q

    I am not sure, but why dont you access for the chars in s derectly like char[i] ?
    Moreover, I dont think it necessary to match with reg expressions, which may be time consuming. Maybe you would like to try code like this:

    a <= 'Z' && a >= 'A' || a <= 'z' && a >= 'a' || a <= '9' && a >= '0'
    

    This way works as judging whether the char is alphanumeric character, while saves time.

    I do a little modification to your code, and it AC:

    public class Solution {
        public boolean isPalindrome(String s) {
            if(s.length()==0){return true;}
            char[] chars = s.toCharArray();
            int i=0;
            int j=chars.length-1;
            while(j>=i){
                String iChar=String.valueOf(chars[i]);
                String jChar=String.valueOf(chars[j]);
                if(!isvalid(chars[i])||!isvalid(chars[j])){
                    if(!isvalid(chars[i])){i++;}
                    if(!isvalid(chars[j])){j--;}
                }
                else{
                    if(!equal(chars[i], chars[j])){
                        return false;
                    }
                    i++;
                    j--;
                }
            }
            return true;
        }
        public boolean isvalid(char a) {
            return (a <= 'Z' && a >= 'A' || a <= 'z' && a >= 'a' || a <= '9' && a >= '0');
        }
        boolean equal(char a, char b){
    		return (a == b || a - b == 'A' - 'a' || a - b == 'a' - 'A');
    	}
    }
    

    as a mater of fact, toLowerCase is also method that consumes too much time.


  • 0
    M

    equal(a,b) is highly dangerous. a-b=='a'-'A' only means a is 39 greater than b. That works if both are alphabetic, and for all current test cases that is true, but since numeric values are allowed in this solution, a='P', b='3' will pass that test. Both 'P' and '3' pass the isvalid() test, and then are treated as equal in the equal() test.


  • 0
    Q

    Well, you are right.
    But it works for all situations if we modify equal a little, i.e., consider alphabetic and numeric respectively.
    Maybe we should recommend add such test cases as you said to this problem


Log in to reply
 

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