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.
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.
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])
@StefanPochmann Why is collections.Counter much slower? Thanks.
@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?
we have O(n) to loop through the array
Which array is O(n)? Note that:
string.ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
@dongning You're right, my bad. I guess it is:
= O(26) * (O(n) to find + O(n) to count)
= O(1) * O(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 =  * 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 if len(result) else -1
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.