409. Longest Palindrome

1. Longest Palindrome

解题思路：

1. 找最大回文字符串
2. 使用 set 的集合不重复的性质
3. 遍历字符串，不在set中，则放进去
4. 在set中，计数加2
5. 结果要考虑字符串长度在 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