Finding a substring in a jumbled string

Question

I am writing a script - includes(word1, word2) - that takes two strings as arguments, and finds if word1 is included in word2. Word2 is a letter jumble. It should return Boolean. Also repetition of letters are allowed, I am only checking if the letters are included in the both words in the same order.

>>>includes('queen', 'qwertyuytresdftyuiokn')
True

'queen', 'QwertyUytrEsdftyuiokN'

I tried turning each word into lists so that it is easier to work with each element. My code is this:

def includes(w1, w2):
    w1 = list(w1)
    w2 = list(w2)
    result = False
    for i in w1:
        if i in w2:
            result = True
        else:
            result = False
    return result

But the problem is that I need to also check if the letters of word1 comes in the same order in word2, and my code doesn't controls that. I couldn't find a way to implement that with list. Just like I couldn't do this much with strings, so I think I need to use another data structure like dictionary but I don't know much about them.

r.user.05apr · Answer 1 · 2020-03-17T14:06:05.760

2

If you are not just checking substrings:

def include(a, b):
    a = "".join(set(a)) # removes duplicates
    if len(a) == 1:
        if a in b:
            return True
        else:
            return False
    else:
        try: 
            pos = b.index(a[0])
            return include(a[1:], b[pos:])
        except:
            return False

print(include('queen', 'qwertyuytresdftyuiokn'))
#True

edited Mar 17 '20 at 14:06

answered Mar 17 '20 at 13:36

r.user.05apr

5,356
3
22
39

Marek R · Accepted Answer · 2020-03-17T14:15:23.783

2

I hope I understood what is your goal.
Python is not my thing, but I think I made it pythonic:

def is_subsequence(pattern, items_to_use):
    items_to_use = (x for x in items_to_use)
    return all(any(x == y for y in items_to_use) for x, _ in itertools.groupby(pattern))

https://ideone.com/Saz984

Explanation:

itertools.groupby transfers pattern in such way that constitutive duplicates are discarded
all items form form grouped pattern must fulfill conditions
any uses generator items_to_use as long as it doesn't matches current item. Note that items_to_use mus be defined outside of final expression so progress on it is kept every time next item from pattern is verified.

edited Mar 17 '20 at 14:15

answered Mar 17 '20 at 13:44

Marek R

32,568
6
55
140

Your code works almost always, but the problem is that it doesn't return true when the first word has the same letter in a row. It should return true even if the letter that is repeated in word1 is found only once in the word2. – arty Mar 17 '20 at 13:56
Fixed, I've missed corner case. – Marek R Mar 17 '20 at 14:02
Thank you very much. Could you explain how you fixed it? I could understand you previous code but not this. – arty Mar 17 '20 at 14:05

Finding a substring in a jumbled string

2 Answers2

Linked