在Python中查找方形数组数的程序
假设我们想要制作一个小写字母的目标字符串。起初,我们有一个长度为n的包含n个“?”标记的序列。我们还有一个小写字母的戳。在每个回合中,我们可以将戳放在序列上,并将其中的每个字母替换为相应的戳中的字母。您最多可以进行10 * n次操作。
例如,考虑初始序列为“?????”,戳为“abc”,那么我们可以在第一轮中制作出“abc??”,“?abc?”,“??abc”等字符串。如果可能对序列进行戳,则返回一个索引的数组,左侧的字母为被戳印的字母。如果不可能,则返回一个空的数组。因此,当序列为“ababc”,戳为“abc”时,答案可能如[0,2],因为我们可以形成“?????” – >“abc?” – >“ababc”。
因此,如果输入为s =“abcd”t =“abcdbcd”,则输出将为[3,0]
要解决此问题,我们将执行以下步骤:
- 如果s的大小与1相同,则
- 当t中所有字符都相同时,返回从0到t的列表,并且它们是s\[0\],否则返回新的空列表
- ans:=一个新列表
-
当t与t号数的“?”标记大小不同时,重复执行以下操作
- tmp:= t
-
对于i在0到s的大小的范围内,执行以下操作
- 对于j在s的大小下降到i + 1的范围内:
-
search:= i个“?”连接s的子字符串\[从下标i到j-1\]连接(s的大小-j)个“?”
-
当search在t中时,执行以下操作:
- 将search存在t中的位置插入到ans的末尾
-
使用s的大小替换search与“?”相同的t仅一次
-
如果t与t号数的“?”标记大小相同,则
- 从循环中出来
- 如果t与t号数的“?”标记大小相同,则
- 从循环中出来
- 如果tmp与t相同,则
-
从循环中出来
- 对于j在s的大小下降到i + 1的范围内:
-
返回ans的反转。
示例
让我们看以下实现,以获得更好的理解
def solve(s, t):
if len(s) == 1:
return [i for i in range(len(t))] if all(t==s[0] for t in t)else []
ans = []
while t != "?" * len(t):
tmp = t
for i in range(len(s)):
for j in reversed(range(i+1, len(s)+1)):
search = "?" * i + s[i:j] + "?" * (len(s)-j)
while t.find(search) != -1:
ans.append(t.find(search))
t = t.replace(search, "?"*len(s), 1)
if t == "?" * len(t): break
if t == "?" * len(t): break
if tmp == t: return []
return ans[::-1]
s = "abcd"
t = "abcdbcd"
print(solve(s, t))
输入
"abcd", "abcdbcd"
输出
[3,0]