Short in Python


  • 50

    This problem is pretty much equivalent to Isomorphic Strings. Let me reuse two old solutions.

    From here:

    def wordPattern(self, pattern, str):
        s = pattern
        t = str.split()
        return map(s.find, s) == map(t.index, t)
    

    Improved version also from there:

    def wordPattern(self, pattern, str):
        f = lambda s: map({}.setdefault, s, range(len(s)))
        return f(pattern) == f(str.split())
    

    From here:

    def wordPattern(self, pattern, str):
        s = pattern
        t = str.split()
        return len(set(zip(s, t))) == len(set(s)) == len(set(t)) and len(s) == len(t)
    

    Thanks to zhang38 for pointing out the need to check len(s) == len(t) here.


  • 0

    Good job! I didn't know continuous equal just like a == b == c works in Python until I see the second code snippet.


  • 0

    Yes, "chained" comparisons are pretty nice. You can do any combination, even longer and silly ones :-)


  • 0
    O

    OMG it's so clever!! I use bidirectional dictionary which takes several lines||| AWESOME


  • 0
    C

    Really short compared with my initial solution!


  • 0
    Z

    Brilliant zip!!!


  • 0

    Great solution, as always :-) Well, at the first glance I just felt like using split and zip very much :-)


  • 0
    Z

    For the second one, I think you should add ''and len(t)==len(s)"" to the return. right?


  • 0

    @zhang38 Oh, yes, you're right. Thanks a lot. Wasn't necessary in the old problem, but here it is (especially now that the tests got updated and actually find that bug :-)


  • 0
    S

    for solution 1, is it possibly time consuming? i think it could has a complexity as $O(n^2)$. Assuming each character in the pattern is unique and each word in the string is unique, then for the second half, each find and index operation would need to iterate through at least half of the pattern or string respectively?


  • 0

    @stpeterh Yes, it's only O(n^2). I added an improved version now.


  • 0

    @stpeterh As the alphabet is (usually) finite, the pattern can't have only unique letters for arbitrarily large n. But map(s.find, s) also takes Θ(n2) time for pattern=anbn.


  • 0
    S

    @StefanPochmann Yes. $a^{n} b^{n}$ is a better example for pattern, considering alphabet is finite. And even if we could fake words, there would be finite words as well, assuming a word could not be infinitely long. So, $a^{n} b^{n}$ is a better example for string too. Thanks for your nice solutions.


  • 0
    P

    Could you explain what f = lambda s: map({}.setdefault, s, range(len(s))) does behind the scene, especially the part within map()? Appreciate it.


  • 1

    @psnr Let me rewrite it in equivalent "simpler" Python.

    def f(sequence):
        first_occurrence = {}
        normalized = []
        for i, item in enumerate(sequence):
            if item not in first_occurrence:
                first_occurrence[item] = i
            normalized.append(first_occurrence[item])
        return normalized
    

    Does that help? Perhaps also check out the documentation for map and dict.setdefault.


  • 0
    C

    setdefault(...), D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D, setdefault() is just a mthod of dict.


  • 0
    P

    helps a lot. thanks


  • 0
    I

    If I use:

    def wordPattern(self, pattern, str):
        f = lambda s: map(dict.setdefault, s, range(len(s)))
        return f(pattern) == f(str.split())
    

    I will get this error message:

    TypeError: descriptor 'setdefault' requires a 'dict' object but received a 'unicode'
    

    But, if I change dict.setdefault to dict().setdefault. It will be good.

    def wordPattern(self, pattern, str):
        f = lambda s: map(dict().setdefault, s, range(len(s)))
        return f(pattern) == f(str.split())

  • 0

    the first solution, why s use 'find' method but t use 'index' ? could i both use 'index'?


  • 0

    @hotea No, t is a list and thus doesn't have a find method. Did it actually work when you tested it?


Log in to reply
 

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