試圖了解我們如何確定第二個字串（S2）是否與第一個字串（s1）遵循相同的字母順序（無論是從左到右還是從右到左）：
例子：
-
qwer asdf Answer:No -
abcdefghi dfge Answer: No -
qwkedlrfid kelid Answer: Yes -
abcdefghi hcba Answer: Yes -
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")
uj5u.com熱心網友回復：
您可以自己實作基于堆疊的回溯機制，或者對每個字母遞回執行。
我只是選擇讓 Python 的正則運算式引擎來完成這項作業：
import re
def check_contains(s1, s2):
regex = f"{'.*'.join(s2)}|{'.*'.join(reversed(s2))}"
return bool(re.search(regex,s1))
我基本上創建了一個正則運算式，搜索每個字母之間用任何東西分隔，反之亦然。
我冒昧地改進了@Timus 的回答。不幸的是，正如我所預料的，我的正則運算式解決方案會導致對長輸入的災難性回溯。防止它并不簡單，因為它需要為每個角色創建一個組或使用外部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.
uj5u.com熱心網友回復：
這是一個沒有正則運算式但字串切片的版本，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。）
我玩過一些性能測量：在我看來，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
但也許我犯了一個錯誤......
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/379980.html
上一篇：二叉樹不插入或搜索節點