2 lines Java using Regex


  • 16

    Regex idea from andrei3's solution.

    public boolean isValidSerialization(String preorder) {
        String s = preorder.replaceAll("\\d+,#,#", "#");
        return s.equals("#") || !s.equals(preorder) && isValidSerialization(s);
    }

  • 0
    K
    This post is deleted!

  • 0
    K

    One-line Python solution considering ord('#') < ord('0'), but not efficient...

    def isValidSerialization(self, preorder):
        return preorder == '#' or re.sub(r'\d+,#,#', '#', preorder) < preorder and self.isValidSerialization(re.sub(r'\d+,#,#', '#', preorder))

  • 0

    Meh, computing the same thing twice is ugly, and long lines needing scrolling are uglier.
    But I like the < :-)

    Using two lines:

    def isValidSerialization(self, preorder):
        s = re.sub('\d+,#,#', '#', preorder)
        return s == '#' or s < preorder and self.isValidSerialization(s)

  • 0
    E

    Nice solution using Regex, but what's the time complexity?


  • 0

    What do you think it is?


  • 0
    E

    It looks like O(n) to me, but I am not very familiar with replaceAll. If replaceAll is of O(n), since every time the string is roughly compressed to half, then it looks like O(n).


  • 0
    F

    worst case O(n^2). The idea is constantly removing leaves and replacing leaves with Null. Take the example, "1#2#3#...n##", basically it's a tree whose internal nodes only have right son. It takes n times isValidSerialization call and each call is O(n) by using replaceAll.


  • 0
    E

    @fetcher It makes sense. Thanks.


  • 0

    @fetcher Yep, only O(n^2), and that example is equivalent to the one I also gave andrei3 :-). I thought about using "(\\d+,#,)+#" which would solve it quickly, but it would still be slow for "always only left child" and I'm guessing also for lots of less simple cases, so I gave up trying to make it fast and just went for making it simple.


  • 0
    A

    Would you point out why the c++ regex is not work?

    bool isValidSerialization(string preorder) {
        regex e("\\d,#,#");
        string test = preorder;
        std::regex_replace(test, e, "#");
        cout << test << endl;
        return test == "#" || (test != preorder && isValidSerialization(test));
    }

  • 0

    @angrybirdRR You're ignoring the result. Do test = regex_replace(test, e, "#");. And add the missing + in the regex.


  • 0
    A

    thanks! works!


  • 0
    C

    I have exactly same idea with you! The only difference is I used iteration. It's concise, but time complexity is not as good as indegree count solution.

    public boolean isValidSerialization(String preorder) {
    if(preorder==null || preorder.isEmpty()) return false;
    while(preorder.matches("(.)\d+,#,#(.)")){
    preorder=preorder.replaceAll("\d+,#,#", "#");
    }
    return preorder.equals("#");
    }


Log in to reply
 

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