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")

CodePudding user response：

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 doubt there's a better solution. You must take care of so many edge cases that an O(n^n) is sort of a must. If someone else has a better idea, you're welcome to chime in.

CodePudding user response：

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

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 ...