试图了解我们如何确定第二个字符串(S2(是否与第一个字符串(s1(遵循相同的字母顺序(无论是从左到右还是从右到左(：
示例：
qwer asdf Answer:Noabcdefghi dfge Answer: Noqwkedlrfid kelid Answer: Yesabcdefghi hcba Answer: Yesabacdfeag bca Answer:Yes (based on the last 'a' in the first string)
有一件事有助于将结果过滤为"0"；否"；如果字符串2中的项在字符串g1中不存在；不；。。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的回答。不幸的是，正如我所预料的那样，我的regex解决方案会导致长输入出现灾难性的回溯。防止它并不简单，因为它需要为每个字符创建一个组或使用外部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行解决方案，但我添加了注释、文档、doctesting和优化，并使其为生产做好了准备。你可以随心所欲：
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
EDIT: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。(
我在性能测量方面做了一些尝试：在我看来，在你提供的字符串类型方面，Bharel的版本比这个版本有优势。当要搜索的字符串变大时，这种情况似乎会发生变化。我尝试了以下方法(check_contains_1是Bharel的解决方案，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
但也许我犯了一个错误。。。