Algorithms




Pay Notebook Creator: Elaine Chan0
Set Container: Numerical CPU with TINY Memory for 10 Minutes 0
Total0
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']