# Short Python solutions

• ``````def findLongestWord(self, s, d):
def isSubsequence(x):
it = iter(s)
return all(c in it for c in x)
return max(sorted(filter(isSubsequence, d)) + [''], key=len)
``````

More efficient version (no sorting):

``````def findLongestWord(self, s, d):
def isSubsequence(x):
it = iter(s)
return all(c in it for c in x)
return min(filter(isSubsequence, d) + [''], key=lambda x: (-len(x), x))
``````

Different style:

``````def findLongestWord(self, s, d):
best = ''
for x in d:
if (-len(x), x) < (-len(best), best):
it = iter(s)
if all(c in it for c in x):
best = x
return best
``````

Optimized as suggested by @easton042, testing from longest to shortest and returning the first valid one without testing the rest:

``````def findLongestWord(self, s, d):
def isSubsequence(x):
it = iter(s)
return all(c in it for c in x)
d.sort(key=lambda x: (-len(x), x))
return next(itertools.ifilter(isSubsequence, d), '')
``````

Or:

``````def findLongestWord(self, s, d):
for x in sorted(d, key=lambda x: (-len(x), x)):
it = iter(s)
if all(c in it for c in x):
return x
return ''
``````

And taking that even further by not sorting unnecessarily much:

``````def findLongestWord(self, s, d):
heap = [(-len(word), word) for word in d]
heapq.heapify(heap)
while heap:
word = heapq.heappop(heap)[1]
it = iter(s)
if all(c in it for c in word):
return word
return ''``````

• @StefanPochmann Your code is always mind blowing...

• Here's something a little different. You can build a 2D map of the input string which maps at each index characters `'a' - 'z'` pointing to the next occurrence of that char. Then test each string in the dictionary using the map to skip to the next char. I use `-1` to denote that there is no next char. If you get through the dictionary word without hitting a `-1` that dictionary word is valid. I didn't sort the dictionary but you could, I just check each word and pick the best.

``````    public string FindLongestWord(string s, IList<string> d)
{
int[,] map = new int[s.Length+1, 26];
for (int col = 0; col < 26; col++) map[s.Length,col] = -1;

for (int i = s.Length - 1; i >= 0; i--)
{
for (int col = 0; col < 26; col++)
{
map[i,col] = map[i+1,col];
}
map[i, s[i]-'a'] = i+1;
}

string best = "";
foreach (string x in d)
{
if (x.Length < best.Length) continue;

int dIndex = 0;
foreach (char c in x)
{
dIndex = map[dIndex,c-'a'];
if (dIndex == -1) break;
}

if (dIndex != -1)
{
if (x.Length > best.Length || (x.Length == best.Length && string.Compare(x, best) == -1)) best = x;
}
}

return best;
}
``````

• For the sake of performance, you can filter from the longest string and return before testing all strings.

• The built-in function `iter()` takes an iterable object and returns an iterator.
• with state that remembers where it is during iteration,
• `c in it` returns `True` if the value in the iteration and updates the state to point at the next value
• return `False` when it goes to the end of iteration

just for those who are not familiar with `iter()` at first like me.

• @easton042 Right, thanks. I just added two solutions that do that.

• I love the last solution.
But the second from last doesn't seem working as wish, I guess you mean this:
`return next(ifilter(isSubsequence, d), '')`

• @easton042 What do you mean "doesn't seem working as wish"? It works for me and it does get accepted.

• `return next(iter(filter(isSubsequence, d)), '')`
this statement in face applies `isSubsequence` to every element of `d`, instead of only finds out the first one that can pass the test. So I think the right way to iterate is like this:
`return next(ifilter(isSubsequence, d), '')`

• @easton042 Oh wow, that is embarrassing. You're right, using `filter` was nonsense. And I just mindlessly wrapped `iter` around it because Python complained without it. I should've turned on my brain instead. Sorry I got that wrong, I replaced it with `itertools.ifilter` now. And added a not-so-functional version as well.

• Hi @StefanPochmann, Thanks for your solution. I see several of your answers using the function `isSubsequence`. Could you spend some time explain the logic of this function here? Especially why we need `it = iter(s)`. I am confused about why we need to convert `s` to an iterator each time I see the function used for solving different problems. Thanks in advance.

• @0x0101 Because while I'm going through x, I want to go through s only once. Overall. If I used s directly, I'd search through s from its start for every character in x. Which is wrong.

• I really like this elegant line, thanks again!

``````(-len(x), x) < (-len(best), best)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.