# Python Simple (Two pointer)

• Let's check whether each word is a subsequence of S individually by "best" order (largest size, then lexicographically smallest.) Then if we find a match, we know the word being considered must be the best possible answer, since better answers were already considered beforehand.

Let's figure out how to check if a needle (word) is a subsequence of a haystack (S). This is a classic problem with the following solution: walk through S, keeping track of the position (i) of the needle that indicates that word[i:] still remains to be matched to S at this point in time. Whenever word[i] matches the current character in S, we only have to match word[i+1:], so we increment i. At the end of this process, i == len(word) if and only if we've matched every character in word to some character in S in order of our walk.

``````def findLongestWord(self, S, D):
D.sort(key = lambda x: (-len(x), x))
for word in D:
i = 0
for c in S:
if i < len(word) and word[i] == c:
i += 1
if i == len(word):
return word
return ""
``````

• Thanks for your elegant solution!

• The same idea using python build-in function:

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

• Thanks for a simple and easy-to-understand explanation! Sometimes other people are so good and post answers that are super short/hard-to-understand. Thanks for keeping it real.

• Here is my naive implementation

``````class Solution(object):
def findLongestWord(self, s, d):
"""
:type s: str
:type d: List[str]
:rtype: str
"""
def is_subsequence(s,t):
# check if t is subsequence of s
i = 0
j = 0

m = len(s)
n = len(t)

if n > m:
return False

while i < m and j < n:
if s[i] == t[j]:
i += 1
j += 1
else:
i += 1
return j == n

subsequence_length = 0
subsequence = ''
for string in d:
if is_subsequence(s,string):
if subsequence_length < len(string):
subsequence = string
subsequence_length = len(string)
elif subsequence_length == len(string):
subsequence = min(subsequence,string)
return subsequence``````

• great solution!

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