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 [ ]:

In [19]:

w.index('a')

Out[19]:

In [22]:

w[w.index('b') + 1:]

Out[22]:

['e']

In [ ]:

Pay Notebook Creator: Elaine Chan	0
Set Container: Numerical CPU with TINY Memory for 10 Minutes	0
Total	0

Algorithms