Блог

Пытаясь понять, как мы можем определить, соответствует ли вторая строка (S2) тому же алфавитному порядку или нет, что и первая строка (s1) (независимо от того, идет ли она слева направо или справа налево):

примеры:

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)
    

Одна вещь, которая помогает фильтровать результаты на «Нет», заключается в том, что если элемент в string2 не существует в string1, это автоматически означает «Нет» ..exp 1)

очевидно, что мой код не завершен и не возвращает правильные ответы, но поскольку сообщество обычно хочет, чтобы некоторые усилия были направлены на то, чтобы поделиться тем, что у меня есть до сих пор … и не уверен, как поступить…

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

Вы можете реализовать механизм обратного отслеживания на основе стека самостоятельно или сделать это рекурсивно для каждой буквы.

Я просто решил позволить движку регулярных выражений Python выполнять эту работу:

 import re

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

Я в основном создаю регулярное выражение для поиска каждой из букв, разделенных чем-либо промежуточным, и то же самое для обратного.

Я взял на себя смелость улучшить ответ @Timus’es. К сожалению, как я и ожидал, мое решение для регулярных выражений приводит к катастрофическому возврату при длинных вводах. Предотвратить это непросто, поскольку для этого требуется создать группу для каждого символа или использовать внешний regex модуль, оба из которых мне не нравятся.

Вот улучшенная версия, которая представляет собой O (n) (самый быстрый из возможных способов):

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

Имейте в виду, что технически это 8-строчное решение, но я добавил комментарии, документацию, проверку, оптимизацию и подготовил его к производству. Вы можете изменить его по своему вкусу:

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

В качестве дополнительного бонуса — если вы хотите узнать положение букв, просто замените functools.reduce на itertools.accumulate .

Вот версия без регулярных выражений, но нарезка строк и str.find вместо:

 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)
 

Ваши примеры:

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

Результат:

 False
False
True
True
True
 

РЕДАКТИРОВАТЬ: check является очевидным кандидатом для рекурсивной реализации, которая более компактна и работает в том же диапазоне:

 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:])
 

(Добавлена также проверка if len(s1) < len(s2): return False работоспособности.)

Я немного поиграл с измерением производительности: мне кажется, что версия Барела имеет преимущество перед этой для тех строк, которые вы предоставили. Кажется, это меняется, когда строки для поиска становятся больше. Я пробовал следующее ( check_contains_1 это решение Барела, check_contains_2 то, что указано в этом ответе):

 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)
 

Вывод:

 Version 1: 1.85 secs
Version 2: 0.04 secs
True
 

Но, возможно, я допустил ошибку…