AC Python one pass, two solutions


  • 0
    def wordPattern(self, pattern, string):
        words = string.split()
        if len(pattern) != len(words):
            return False
        d = {}
        b = 0
        for char, word in zip(pattern, words):
            x = 1 << ord(char) - ord('a')
            if (word in d and d[word] != x) or (word not in d and b & x):
                return False
            b |= x
            d[word] = x
        return True
    
    def wordPattern2(self, pattern, string):
        words = string.split()
        if len(pattern) != len(words):
            return False
        d = {}
        b = set()
        for char, word in zip(pattern, words):
            if (word in d and d[word] != char) or (word not in d and char in b):
                return False
            b.add(char)
            d[word] = char
        return True
    
    
    # 26 / 26 test cases passed.
    # Status: Accepted
    # Runtime: 36 ms
    

    There are pretty short versions of python solution out there, but they are not one pass. Here are two one pass solution (if using zip doesn't count as a pass, we can avoid zip if it does). We use a dict for the words and we can use either a 32 bit or a hash set for the patterns. Both pretty fast.

    PS:Thanks Stefan for the tips on zip and correction.


  • 0

    Have you considered for letter, word in zip(pattern, words)?


  • 0

    Oh and both of your solutions are wrong, they fail for example pattern="ab", str="dog dog".


  • 0

    Thanks Stefan for catching this. I have just published your test case.


  • 0

    Writing in python for a month now, i never used zip before. Is it still one pass if we use zip? i thought zip pass through the iterables and build the tuples which makes it two pass. The solution is corrected according to your example. Thanks a lot Stefan. I found i could always learn things from you~.


  • 0

    Well, yes, in some sense it's two passes. The first one is zip building a list (since we have Python 2 here). But that's just zip doing it's job. Your actual solution is still just one pass (over that list), and the zip doesn't provide an algorithmic advantage. So I think calling it a one pass solution is fully ok.

    There are problems/solutions where doing it in one pass is actually hard or impressive. For example the Candy problem or this interesting solution (it's a real shame it got downvoted). But here, using zip is just a convenience and it makes the code nicer, more pythonic. Algorithmically, it's the same.

    You present it as "one pass" to distinguish it from for example my "one-liners", right? They're really something different and not single pass. Especially the find/index one, which is n-pass and takes O(n^2) time :-). So since that's the reason you're calling yours one pass, I'd say it's not only ok but actually good.


Log in to reply
 

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