Pattern search by NOT using Regex algorithm and code in python

Question

Today I had an interview at AMD and was asked a question which I didn't know how to solve it without Regex. Here is the question:

Find all the pattern for the word "Hello" in a text. Consider that there is only ONE char can be in between letters of hello e.g. search for all instances of "h.ello", "hell o", "he,llo", or "hel!lo".

Answer 1

Since you also tagged this question algorithm, I'm just going to show the general approach that I would take when looking at this question, without including any language tricks from python.

1) I would want to split the string into a list of words

2) Loop through each string in the resulting list, checking if the string matches 'hello' without the character at the current index (or if it simply matches 'hello')

3) If a match is found, return it.

Here is a simple approach in python:

s = "h.ello hello h!ello hell.o none of these"

all = s.split()

def drop_one(s, match):
    if s == match:
        return True # WARNING: Early Return
    for i in range(len(s) - 1):
        if s[:i] + s[i+1:] == match:
            return True

matches = [x for x in all if drop_one(x, "hello")]
print(matches)

The output of this snippet:

['h.ello', 'hello', 'h!ello', 'hell.o']