题解 | #密码截取#

密码截取

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))


全部评论

相关推荐

某牛奶:一觉醒来全球程序员能力下降200%,小伙成功scanf惊呆在座个人。
点赞 评论 收藏
分享
拉丁是我干掉的:把上海理工大学改成北京理工大学。成功率增加200%
点赞 评论 收藏
分享
服从性笔试吗,发这么多笔,现在还在发。
蟑螂恶霸zZ:傻 x 公司,发两次笔试,两次部门匹配挂,
投递金山WPS等公司10个岗位 >
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务