409. Longest Palindrome
- Longest Palindrome
解题思路:
- 找最大回文字符串
- 使用 set 的集合不重复的性质
- 遍历字符串,不在set中,则放进去
- 在set中,计数加2
- 结果要考虑字符串长度在 0,1,2 的特殊情况
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: int
"""
s_set = set()
count = 0
for i in list(s):
if i in s_set:
s_set.remove(i)
count += 2
else:
s_set.add(i)
j = len(s_set)
if j == 0 :
return count
else:
return count + 1
# A naive recursive solution
def fib(n):
if n == 1 or n == 2:
result = 1
else:
result = fib(n-1) + fib(n-2)
return result
# A memoized solution
def fib_2(n, memo):
if memo[n] is not None:
return memo[n]
if n == 1 or n == 2:
result = 1
else:
result = fib_2(n-1, memo) + fib_2(n-2, memo)
memo[n] = result
return result
def fib_memo(n):
memo = [None] * (n + 1)
return fib_2(n, memo)
# A bottom-up solution
def fib_bottom_up(n):
if n == 1 or n == 2:
return 1
bottom_up = [None] * (n+1)
bottom_up[1] = 1
bottom_up[2] = 1
for i in range(3, n+1):
bottom_up[i] = bottom_up[i-1] + bottom_up[i-2]
return bottom_up[n]
参考链接:
What Is Dynamic Programming and How To Use It:
https://www.youtube.com/watch?v=vYquumk4nWw
请多多指教。
文章标题:409. Longest Palindrome
本文作者:顺强
发布时间:2017-11-01, 23:59:00
原始链接:http://shunqiang.ml/leetcode-409-longest-palindrome/版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。