I am trying to find the first unique character in a string. It is a leetcode problem found here: https://leetcode.com/problems/first-unique-character-in-a-string/
Here is my code so far:
class Solution(object):
def firstUniqChar(self, s):
"""
:type s: str
:rtype: int
"""
hashmap = {x: 0 for x in list(s)}
for char in s:
hashmap[char] = 1
for k, v in hashmap.items():
if v == 1:
index = s.index(k)
return index
The problem is when I split the string into the dictionary values the dictionary automatically places the characters in the string into alphabetical order.
Here is the output when I split the input string ---leetcode--- into a list:
[u'l', u'e', u'e', u't', u'c', u'o', u'd', u'e']
but when i print out the dictionary is shows this:
{u'c': 0, u'e': 0, u'd': 0, u'l': 0, u'o': 0, u't': 0}
notice how the duplicate characters are removed and it is sorted.
Now what is weird is that when running the same function in VScode the dictionary does not sort the list and my implementation works. Also it does not have the weird 'u' added.
Maybe its a leetcode problem because i do not know why it adds the 'u' into the list and dictionary.
Your help is appreciated. Thanks in advance.
Edit:
i need the dictionary to have the same order as the original string so i can find the FIRST non-repeating element in this case which is l not t nor c nor d nor o
CodePudding user response:
You don't need to keep track of the order of the characters in the input string. You need to keep track of the index of the unique characters and return the smallest positive index.
class Solution:
def firstUniqChar(self, s: str) -> int:
seen = {}
for i, c in enumerate(s):
if seen.get(c) is not None:
# This is not a unique character.
seen[c] = -1
else:
seen[c] = i
try:
return min([rc for rc in seen.values() if rc >= 0])
except:
# If the list comp. above results in an empty list,
# catch the exception and return -1.
return -1
CodePudding user response:
The fact that you see a "weird 'u'" added before each string tells you that the grading system uses Python 2, where Unicode strings have to be prefixed as such. Knowing this, you cannot rely on dicts retaining insertion order since this behavior was not officially supported until Python 3.7. Instead, use collections.OrderedDict
in place of a dict in order to retain insertion order:
from collection import OrderedDict
...
hashmap = OrderedDict((x, 0) for x in s)