题解 | #密码截取#

密码截取

http://www.nowcoder.com/practice/3cd4621963e8454594f00199f4536bb1

暴力破解用例只过20个
def Catcher_b(s):
	n = len(s)
	maxlen = 1
	for i in range(n):
		for j in range(i,n+1):
			if s[i:j] == s[i:j][::-1]:
				curlen = j - i
			if maxlen < curlen :
				maxlen = curlen
	return maxlen

s = input().strip()
print(Catcher_b(s))


动态规划用空间换时间
def Catcher(s):
	n = len(s)
	if n == 1 :
		return n
	dp = [[False for _ in range(n)] for _ in range(n)]
	maxlen = 1
	for j in range(1,n):
		for i in range(j):
			if j - i <=2 :
				if s[i] == s[j]:
					dp[i][j] = True
					curlen = j - i + 1
					# print(curlen)
			else:
				if s[i] == s[j] and dp[i+1][j-1]:
					dp[i][j] = True
					curlen = j - i + 1
					# print(curlen)
			if dp[i][j]:
				if maxlen < curlen :
					maxlen = curlen
				
	return maxlen
	# for i in dp:
	# 	print(i)
s = input().strip()
print(Catcher(s))


全部评论

相关推荐

门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
05-16 11:16
已编辑
东华理工大学 Java
牛客73769814...:盲猜几十人小公司,庙小妖风大,咋不叫她去4️⃣呢😁
牛客创作赏金赛
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务