Skip to content

Instantly share code, notes, and snippets.

@jessedhillon
Created May 19, 2013 07:40
Show Gist options
  • Save jessedhillon/5606980 to your computer and use it in GitHub Desktop.
Save jessedhillon/5606980 to your computer and use it in GitHub Desktop.
First, the *good* answer is just a cleaned up version of your solution -- the main difference is that I'm leveraging the ability of Python `for ... in` loops to iterate through a string. The *better?* answer uses another optimization (or is it really optimized?) -- try and understand what it's doing.
# return the first non repeated character in a string
def find_original(string):
count_dict = {}
order = []
for char in string:
if char in count_dict:
count_dict[char] += 1
else:
count_dict[char] = 1
order.append(char)
for x in order:
if count_dict[x] == 1:
return x
return None
# good
def find_original(s):
counts = {}
for c in s:
counts[c] = counts.get(c, 1)
for c in s:
if counts[c] == 1:
return c
return None
# better?
def find_original(s):
positions = {}
counts = []
for i, c in enumerate(s):
if not c.isalpha():
continue
positions[c] = positions.get(c, len(counts))
position = positions[c]
if len(counts) <= position:
counts.append((c, 1))
else:
count = counts[position]
counts[position] = (count[0], count[1] + 1)
for c, count in counts:
if count == 1:
return c
return None
tests = [
('catattack', 'k'),
('banana', 'b'),
('racecar', 'e'),
('order rowena', 'd')
]
for s, answer in tests:
value = find_original(s)
assert value == answer, "{0}: expected {1}, got {2}".format(s, answer, value)
print "{0!r} -> {1!r}".format(s, value)
@jessedhillon
Copy link
Author

You may want to look up dict.get() to see what it does: http://www.tutorialspoint.com/python/dictionary_get.htm

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment