1-liners in Python, 76ms


  • 10
    O
    class Solution(object):
        def firstUniqChar(self, s):
            return min([s.find(c) for c in string.ascii_lowercase if s.count(c)==1] or [-1])
    

    It gave me 76ms.

    Or

    class Solution(object):
        def firstUniqChar(self, s):
            return min([s.find(c) for c,v in collections.Counter(s).iteritems() if v==1] or [-1])
    

    which is slower.


  • 2

    Not a short one-liner or any good at all, but maybe a little interesting / puzzling:

    def firstUniqChar(self, s):
        ctr = collections.defaultdict(lambda: s.count(c))
        return ([i for i, c in enumerate(s) if ctr[c] < 2] or [-1])[0]

  • -1
    H

    @StefanPochmann Why is collections.Counter much slower? Thanks.


  • 0
    H

    @o_sharp And why is your first solution so fast? I'm trying to switch to python recently and I'm having a hard time analyzing run-time complexity of these one-liners...

    For example if I take the run-time complexity of each of those methods you used, we have O(n) to loop through the array, then O(n) for each character to get the count, and then O(n) to find the first index of that character. This seems like O(n^2) but it's clearly not the case because the run-time is very fast - Python must optimize it. But how do I know exactly what happens?


  • 0
    W
    This post is deleted!

  • 1
    W

    @hide
    we have O(n) to loop through the array
    Which array is O(n)? Note that:
    string.ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'


  • -1
    H

    @dongning You're right, my bad. I guess it is:
    = O(26) * (O(n) to find + O(n) to count)
    = O(1) * O(n)
    = O(n)


  • -1
    N

    Another Python's black magic. I'm just out of mind why traverse through s 26 times is much faster than traverse it 1 or 2 times using dict or a list-based hash-table. Is it because the underlying traverse process of string is much faster than dict look up or random access of list?

    Here are two solutions with the same idea from other Java or C++ topics, but they takes more than 200 ms to run.

    class Solution(object):
        def firstUniqChar(self, s):
            table = [0] * 128
            
            for char in s:
                table[ord(char)] += 1
                   
            for index, char in enumerate(s):
                if table[ord(char)] == 1:
                    return index
                    
            return -1 
    
    class Solution(object):
        def firstUniqChar(self, s):
            table = collections.OrderedDict()
            duplicate = set()
            
            for index, char in enumerate(s):
                if char in table:
                    duplicate.add(char)
                else:
                    table[char] = index
            result = [val for key, val in table.items() if key not in duplicate]
            return result[0] if len(result) else -1
    

  • -1
    A

    what's the function min() for?


  • -1
    A

    @StefanPochmann
    Can you explain why you use the ctr ?
    I think you can avoid using it and replace ctr[c] with s.count(c).


  • -1

    @adorn331 That gives me "Time Limit Exceeded". Did you truly get that accepted?


Log in to reply
 

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