maybe regex is not a bad idea


  • 1
    H

    a very direct answer but it still very slow...

    public class Solution {
        public boolean isValidSerialization(String preorder) {
            int len=preorder.length();
            if(len==1&&preorder.charAt(0)=='#')return true;
            if(len<3)
            return false;
    
            while(preorder.length()!=1){
                preorder=preorder.replaceAll("[0-9]+,#,#","#");
                if(preorder.length()==len&&len!=1){
                    return false;
                }
                len=preorder.length();
            }
            return true;
        }
    }
    
    

  • 0
    S

    How's it compared to other Java? I use similar approach in python and beats 78%, so I'd say it's not "very" slow, just not the best, but not so bad, either.


  • 0
    H

    @ShawnLMP
    for java this answer is in 4.64%....and it shows spend 31ms


  • 1
    N

    A much simpler version using regex:

      // using regex
        public boolean isValidSerializationRegex(String preorder) {
    
            while(true) {
                preorder = preorder.replaceAll("\\d+,#,#", "#");
                int y = preorder.lastIndexOf("#,#");
    
                // if y == -1, that means we could not find any occurrence of #,#
                // if y == 0 or 1, we should break because we are done replacing #,# to #
                if(y <= 1) break;
    
                // this is to handle cases where we have input like 1,#,#,#,# (basically more nulls than required)
                if(y == 2 && preorder.charAt(y - 2) == '#') break;
            }
    
            return preorder.equals("#");
        }
    

  • 0
    A

    @huaiyan Of course this is costly, because in every loop you create a new string. Suppose the string has 100,000 characters, the copy alone would take huge amount of time.


  • 0
    H

    @ayuanx I think that should be the right answer. To improve this I searched StringBuilder class, but there is no likely method.....


Log in to reply
 

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