python-将字符串“标记”为所需字符串的最佳方法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python-将字符串“标记”为所需字符串的最佳方法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2662字，纯文字阅读大概需要4分钟。
内容图文
因此,我正在寻找以下问题的算法：
系统会为您提供所需的字符串s和标记t. t也是一个字符串.令开始的字符串为len *(s)*“？”.
是否可以使用戳记使用戳记将起始字符串转换为字符串s？整个图章必须位于开头的字符串内(图章的边界不得超过????? …字符串的边界).
打印所需数量的图章,并为每个图章打印图章的左边框.
例：
AABCACA (desired result)
ABCA (stamp)
Solution:
3
1 4 2
explanation: ??????? → ABCA??? → ABCABCA → AABCACA.
我的解决方案：
如果图章的首字母不是所需字符串的首字母,则无法执行此任务.最后一个字母也是如此.如果戳记未在所需字符串中包含所有字母,则该任务是不可能的.
我的算法是这样的：尝试在所需的字符串中找到图章.如果找到它,请将其删除并用问号替换.标记图章的左边框.尽可能做到这一点.
然后寻找大小为len(stamp)-1的图章的连续子数组.如果发现其中任何一个,请将其删除并替换为问号.标记图章的左边框.
然后寻找大小为len(stamp)-2的图章的连续子数组.如果发现其中任何一个,请将其删除并替换为问号.标记图章的左边框.这样做直到完成.那里您有答案.
问题所在
我不确定我的代码有什么问题,因为它似乎无法通过一些测试用例.可能存在逻辑错误.
import sys
desiredString = input()
stamp = input()
stampingSpots = []
if (len(set(desiredString)) != len(set(stamp)) or stamp[0] != desiredString[0] or stamp[-1] != desiredString[-1]):
print("-1")
sys.exit()
def searchAndReplace(stringToFind, fix): #Search for stringToFind and replace it with len(stringToFind)*"?". Fix is used to fix the position.
global desiredString
for x in range(0, len(desiredString)-len(stringToFind)+1):
if desiredString[x:x+len(stringToFind)] == stringToFind:
stampingSpots.append(x+1-fix) #Mark down the stamping spot
firstPart = desiredString[:x]
firstPart += len(stringToFind)*"?"
firstPart += desiredString[len(firstPart):]
desiredString = firstPart
return True
return False
while(searchAndReplace(stamp,0)): #Search for the full stamp in desiredString
searchAndReplace(stamp,0)
length = len(stamp)-1
while(length > 0):
for firstPart in range(0, len(stamp)-length+1):
secondPart = firstPart+length
while(searchAndReplace(stamp[firstPart:secondPart], firstPart)):
searchAndReplace(stamp[firstPart:secondPart], firstPart)
if len(stampingSpots) > 10*len(desiredString): #Too much output, not possible
print("-1")
sys.exit()
length -= 1
print(len(stampingSpots))
for i in reversed(stampingSpots):
print(i, end = " ")
解决方法:
您描述的算法从根本上来说是有缺陷的.它产生的结果与图章实际可以做的事情完全不符.例如,对于图章AB和字符串AAA,它将尝试在字符串的边界之外盖章以应用最终的A.它还将尝试将图章ABC的AB和BC子字符串彼此紧挨着使用.字符串ABBC,但没有实际应用的邮票可以做到这一点.
该图章不能用于应用图章字符串的任意子字符串.它可以用于在以前的图章应用程序上盖章,但是您的算法没有考虑过盖章的全部复杂性.同样,即使您可以标记图章字符串的任意子字符串,也没有证明算法会最小化图章应用程序.
内容总结
以上是互联网集市为您收集整理的python-将字符串“标记”为所需字符串的最佳方法全部内容，希望文章能够帮你解决python-将字符串“标记”为所需字符串的最佳方法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。