Created
May 19, 2013 07:40
-
-
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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
You may want to look up
dict.get()
to see what it does: http://www.tutorialspoint.com/python/dictionary_get.htm