# Algorithms

 Pay Notebook Creator: Elaine Chan 0 Set Container: Numerical CPU with TINY Memory for 10 Minutes 0 Total 0
In [ ]:
#crosscompute

In [ ]:
"""
Given a string S and a set of words D, find the longest word in D that is a subsequence of S.

Word W is a subsequence of S if some number of characters, possibly zero, can be deleted from S to form W, without reordering the remaining characters.

Note: D can appear in any format (list, hash table, prefix tree, etc.

For example, given the input of S = "abppplee" and D = {"able", "ale", "apple", "bale", "kangaroo"} the correct output would be "apple"

The words "able" and "ale" are both subsequences of S, but they are shorter than "apple".
The word "bale" is not a subsequence of S because even though S has all the right letters, they are not in the right order.
The word "kangaroo" is the longest word in D, but it isn't a subsequence of S.
"""

In [11]:
S = "abppplee"
D = ["able", "ale", "apple", "bale", "kangaroo"]

In [12]:
w = list(D[4])
print(w)

['k', 'a', 'n', 'g', 'a', 'r', 'o', 'o']

In [13]:
for letter in w:
if letter not in S:
print(letter, 'not in', S)
else:
print(letter, 'in', S)

k not in abppplee
a in abppplee
n not in abppplee
g not in abppplee
a in abppplee
r not in abppplee
o not in abppplee
o not in abppplee

In [14]:
# eliminate words with invalid letters
# eliminate words with letters in wrong order
for i in w:
if i not in S:
print(i, 'not in', S)

k not in abppplee
n not in abppplee
g not in abppplee
r not in abppplee
o not in abppplee
o not in abppplee

In [26]:
# step 1: take each i in w
# check each j in S
# when i == j:
# slice off preceding letters in S
# if len(S) < len(w) - 1, eleminate w
# else, slice off i from w
# if len(w) == 0: append word to result
# if len(w) > 0 and len(S) >= len(w): repeat step 1
# else: go to next word

w = list(D[0])
def yield_match(w, S):
for i in w:
for j in S:
if i == j:
w.pop(w.index(i))
S = S[S.index(j)+1:]
yield i,j

In [28]:
m = yield_match(w, S)

Out[28]:
<generator object yield_match at 0x7fb0ec7612b0>
In [30]:
next(yield_match)

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-30-31a8c02f0f5b> in <module>()
----> 1 next(yield_match)

TypeError: 'function' object is not an iterator
In [19]:
w.index('a')

Out[19]:
0
In [22]:
w[w.index('b') + 1:]

Out[22]:
['e']