strings order (left to right and right to left)

Question

Trying to understand how can we determine if the second string(S2) is following the same alphabetic order or not as the first string(s1) (regardless if its from left to right or right to left):

examples:

1.  qwer
    asdf
   Answer:No
   

2. abcdefghi
   dfge
   Answer: No
   

3. qwkedlrfid
   kelid
   Answer: Yes
   

4. abcdefghi
   hcba
   Answer: Yes
   

5.  abacdfeag 
    bca
    Answer:Yes (based on the last 'a' in the first string)
   

One thing that helps to filter the results to "No" is that if an item in string2 does not exist in string1 that is automatically a "No"..exp 1)

my code is not completed & not returning the right answers obviously but since the community usually want to see some effort thought of sharing what I have so far... and not sure how to proceed...

s1=input()
s2=input()

check=any(items in s1 for items in s2)
if check is not True or s1[-1] >= s2[0]:
 print("NO")
elif s2[-1] <= s1[0]:
 print("YES")

Answer 1

Here's a version without regex but string slicing and str.find instead:

def check(s1, s2):
    i = 0
    for c in s2:  # looping over the characters in s2
        if i < len(s1):
            incr = s1[i:].find(c) + 1  # looking for c in the rest of s1
            if incr == 0:  # c not found
                break
            i += incr
        else:  # end of s1 reached, but still c's to cover
            break
    else:  # loop went through without break -> found
        return True
    return False  # loop exit with break -> not found

def check_contains(s1, s2):
    return check(s1, s2) or check(s1[::-1], s2)

Your examples:

strings = [("qwer", "asdf"), ("abcdefghi", "dfge"), ("qwkedlrfid", "kelid"), ("abcdefghi", "hcba"), ("abacdfeag", "bca")]
for s1, s2 in strings:
    print(check_contains(s1, s2))

Result:

False
False
True
True
True

EDIT: check is an obvious candidate for a recursive implementation, which is more compact and performes in the same range:

def check(s1, s2):
    if not s2:
        return True
    if len(s1) < len(s2):
        return False
    i = s1.find(s2[0]) + 1
    if i == 0:
        return False
    return check(s1[i:], s2[1:])

(Added also the sanity check if len(s1) < len(s2): return False.)

---

I've played a bit around with performance measurement: Seems to me that Bharel's version has an edge over this one for the kind of strings you've provided. This seems to change when the strings to search in get larger. I've tried the following (check_contains_1 is Bharel's solution, check_contains_2 is the one in this answer):

from random import choices, randint
from string import ascii_lowercase as chars
from time import perf_counter

num = 10_000
max_len_1, max_len_2 = 50, 5
strings = [
    (
        "".join(choices(chars, k=randint(2, max_len_1))),
        "".join(choices(chars, k=randint(2, max_len_2)))
    )
    for _ in range(num)
]

start = perf_counter()
result_1 = [check_contains_1(s1, s2) for s1, s2 in strings]
end = perf_counter()
print(f"Version 1: {end - start:.2f} secs")

start = perf_counter()
result_2 = [check_contains_2(s1, s2) for s1, s2 in strings]
end = perf_counter()
print(f"Version 2: {end - start:.2f} secs")

print(result_1 == result_2)

Output:

Version 1: 1.85 secs
Version 2: 0.04 secs
True

But maybe I made a mistake ...

Answer 2

You can implement a stack-based backtracking mechanism yourself, or do it recursively for each letter.

I just chose to let Python's regex engine do the job:

import re

def check_contains(s1, s2):
    regex = f"{'.*'.join(s2)}|{'.*'.join(reversed(s2))}"
    return bool(re.search(regex,s1))

I basically create a regex searching for each of the letters separated with anything in between, and the same for the reversed.

---

I took the liberty of improving over @Timus'es answer. Unfortunately, as I anticipated, my regex solution causes catastrophic backtracking on long inputs. Preventing it is not simple as it requires creating a group for each character or using the external regex module, both of which I don't like.

Here is the improved version, which is an O(n) (the fastest way possible):

from functools import reduce
def check_contains(s1, s2):
    def _inner(s2):
        try:
            reduce(lambda location, letter: s1.index(letter, location + 1), s2, -1)
            return True
        except ValueError:
            return False
    return _inner(s2) or _inner(reversed(s2))

Keep in mind it's technically an 8 line solution, but I added comments, documentation, doctesting, optimizations and made it production ready. You can strip it to your liking:

from functools import reduce
from contextlib import suppress
from typing import Iterable, Reversible, Sequence

def check_contains(s1: Sequence[object], s2: Iterable[object]) -> bool:
    """Check if s1 contains all items of s2 in order
    
    Examples:
        >>> check_contains("abc", "b")
        True
        >>> check_contains("abc", "d")
        False
        >>> check_contains("abc", "ac")  # Skipping the middle letter
        True
        >>> check_contains("abcd", "cbd")  # Incorrect order
        False
        >>> check_contains("aaab", "aaaa")  # Repeating letters
        False
    """
    index = s1.index  # Cache the index method of string (entirely optional)

    # Attempt short circuit. s2 might not allow len().
    with suppress(TypeError):
        if len(s1) < len(s2):
            return False

    # We're using the index method instead of find for short circuit.
    # Must use -1 and location+1, otherwise s2 == "aaaa" will find all a's in
    # same spot. Equivalent to (pseudocode):
    # s2 = "abc"; pos = s1.index(letter, start)
    # x = s1.index("a", 0); x = s1.index("b", x+1); s1.index("c", x+1)
    try:
        reduce(lambda location, letter: index(letter, location + 1), s2, -1)
        return True
    except ValueError:
        return False

# I do not think this function should exist.
def check_contains_including_reversed(
    s1: Sequence[object], s2: Reversible[object]) -> bool:
    """Check if s1 contains all items of s2 in order or reversed order
    
    Exactly like check_contains(), but includes the following examples:
        >>> check_contains_including_reversed("abc", "bc")  # Normal order
        True
        >>> check_contains_including_reversed("abc", "cb")  # Reversed order
        True
        >>> check_contains_including_reversed("abcd", "cbd")  # Incorrect order
        False
    """
    return check_contains(s1, s2) or check_contains(s1, reversed(s2))

As an added bonus - if you wish to know the position of the letters, just replace functools.reduce with itertools.accumulate.