FAQ: Introduction to Strings - Strings and Conditionals (Part Two)

Have not yet encountered dictionary comprehension. That’s awesome! Figured out a list comprehension solution:

>>> def common_letters(short, long):
      if len(short) > len(long): short, long = long, short
      return [l for i, l in enumerate(short) if l in long and l not in short[:i]]

>>> common_letters('impossible', 'impasse')
['i', 'm', 'p', 's', 'e']
>>>

1 Like

That is the natural progression from algo to expression.

I chose the dict comprehension to eliminate the conditional. Dictionaries cannot have duplicate keys (they simply get created or updated) so we end up with a unique list in the end.

1 Like

Not to do any policing… more to make a few notes…

A tiny bit of refactoring (exactly the same thing but shaking it until the loose parts fall off)

def contains(a, b):
  return b in a

…right? Where’s the loop! Conceptually there’s need to step through the small one, and compare each letter to each letter in the big one, and see if it’s possible to go the whole way (a match)

And then this:

new = []
...
i not in new

Use a set, not a list. Sets support insertion and lookup without searching through the values.
In terms of notreallydoingityourself, sets also have exactly this whole thing as a supported operation: intersection
edit: well, actually, for a small sized list this is 100% fine, but if we were to generalize the problem such that we don’t know how many values there may be in it, then definitely set

Oh and it’s twice as long as it needs to be isn’t it? You only need one of those, they look the same and you only run one of them, so there should be only one of them.

An interesting variation is to also include the amount of each letter they have in common. As far as sets go this is called a multiset, it’s more of a dictionary with a count, but with set operations. In python this is called Counter. Counting how many there are of each letter by searching through each word once for each character would be inefficient, it can be done better than that.