Removing duplicate letters from list of words with Python and List Comprehensions

Question

I'm guessing this has quadratic time complexity, \$O(n^2)\,ドル and \$O(2n)\$ for memory complexity. I wonder if I can do something within the list comprehension to just .pop(n) something out of the list instead of relying on a second list. Thoughts?

listx = ['cat', 'dog','rabbit']
listLettersAlreadyFound = []
[[listLettersAlreadyFound.append(letter) for letter in list(word) if letter not in listLettersAlreadyFound] for word in listx]
print listLettersAlreadyFound

• Grajdeanu Alex: Is the order important when we output the final list ? :)
• Heslacher: I have rolled back the last edit. Please see what you may and may not do after receiving answers .

Answer 1

The reason you get \$O(n^2)\$ time complexity is due to you going through listLettersAlreadyFound, whilst checking if the new item is in that. To improve the performance, you could create another set, reducing time complexity to \$O(n)\$.

But before that, listLettersAlreadyFound is long, first list is unneeded, but lettersAlreadyFound is the same as previous_letters. And you should use snake_case rather than CamelCase.

I also find your comprehensions hard to read, you need to space the logic on different lines. Take:

listx = ['cat', 'dog','rabbit']
listLettersAlreadyFound = []
[
 [
 listLettersAlreadyFound.append(letter)
 for letter in list(word)
 if letter not in listLettersAlreadyFound
 ]
 for word in listx
]
print listLettersAlreadyFound

From this it's easy to notice that a comprehension is probably not the best choice here. You don't actually want the list, you only want the side affects from the list. This goes against the spirit of Functional Programming, which is what comprehensions are. And so you should instead just use a simple for loop.

Merging the above all together could get you some \$O(n^2)\$ time complexity code, that also has \$O(2n)\$ memory:

words = ['cat', 'dog','rabbit']
unique_letters = []
previous_letters = set()
for letter in (letter for word in words for letter in word):
 if letter in previous_letters:
 continue
 previous_letters.add(letter)
 unique_letters.append(letter)
print unique_letters

---

Finally if you don't care about the order of the letters, you can change the for loop to be set. And instead just use:

words = ['cat', 'dog','rabbit']
print set(letter for word in words for letter in word)

---

Also .pop(n) will keep the \$O(n^2)\$ time complexity, and so I'd suggest you don't use it, if you really want better memory performance, use a for loop, as it'd keep the code readable, not a list comprehension.

• Grajdeanu Alex: If order is not important, you can also do something like: list(set(''.join(words)))
• Peilonrayz: @Dex'ter I already mentioned that, however I went for comprehensions, if they later use different datatype.
• theMarceloR: Thanks a million for your help guys. I know about "set" but I got this exercise from a book and I thought about trying with list comprehensions before watching the video with the solution: interactivepython.org/runestone/static/pythonds/Introduction/…