题解 | #密码截取#
密码截取
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))
