Leetcode刷题笔记，palindromic strings回文_dp[left][right] = dp[left + 1][right-1] and s[left

516. Longest Palindromic Subsequence 

One possible longest palindromic subsequence is "bb".

class Solution(object):
    def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """
        length = len(s)
        dp = [[0]*length for i in s]
        
        for left in xrange(length-1, -1, -1):
            dp[left][left] = 1
            for right in xrange(left+1, length):
                if s[left] == s[right]:
                    dp[left][right] = dp[left+1][right-1] + 2
                else:
                    dp[left][right] = max(dp[left+1][right], dp[left][right-1])
        return dp[0][length-1]

 

9. Palindrome Number

class Solution(object):
    def isPalindrome(self, x):
        if x < 0:
            return False
        
        ranger = 1
        while x / ranger >= 10:
            ranger *= 10
        
        while x:
            left = x / ranger
            right = x % 10
            
            if left != right:
                return False
            
            x = (x % ranger) / 10
            ranger /= 100
            
        return True

 

647. Palindromic Substrings 求回文，感觉有点难不知道为什么放在DP，不是用DP解

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
       
        n = len(s)
        res = 0
        for i in xrange(len(s)):
            # add itself
            res += 1
            
            # even
            left = i
            right = i + 1
            while left >= 0 and right <= n-1 and s[left] == s[right]:
                res += 1
                left -= 1
                right += 1
                
            # odd
            left = i-1
            right = i+1
            while left >= 0 and right <= n-1 and s[left] == s[right]:
                res += 1
                left -= 1
                right += 1
        
        return res

 5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

class Solution(object):
    def longestPalindrome(self, s):
        self.n = len(s)
        self.long = self.left = 0
        for i in xrange(self.n):
            # even
            self.helper(i, i+1, s)
            self.helper(i-1, i+1, s)
        return s[self.left: self.left+self.long]
    
    def helper(self, l, r, s):
        while 0 <= l and r < self.n and s[l] == s[r]:
            l -= 1
            r += 1
        l += 1
        r -= 1
        if r - l + 1 > self.long:
            self.long = r - l + 1
            self.left = l

131. Palindrome Partitioning

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        res = []
        self.helper(s, [], res)
        return res
 
    def helper(self, s, cur, res):
        if not s:
            res.append(cur)
            return
 
        for i in xrange(1, len(s) + 1):  # 这里要加1
            if self.isPal(s[:i]):
                self.helper(s[i:], cur + [s[:i]], res)
 
    def isPal(self, s):
        return s == s[::-1]

680. Valid Palindrome II 

class Solution(object):
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        left, right = 0, len(s)-1
         
        while left < right:
            if s[left] != s[right]:
                del_left = s[left+1:right+1]
                del_right = s[left:right]
                return del_left == del_left[::-1] or del_right == del_right[::-1]
            else:
                left += 1
                right -= 1
        return True

336. Palindrome Pairs

 思路：

bot: 前缀 b 是回文， 检查对应后缀ot 的颠倒 to， 如果有to to+bot就是回文。 反过来，如果后缀t是回文， 对应前缀bo 颠倒 ob如果存在 bot+ob  就是回文。

class Solution(object):
    def palindromePairs(self, words):
        """
        :type words: List[str]
        :rtype: List[List[int]]
        """
        def check(word):
            return word == word[::-1]
        
        word_idx = {word:i for i, word in enumerate(words)}
        re = []
        for word, i in word_idx.items():
            for j in xrange(len(word)+1):
                prefix = word[:j]
                suffix = word[j:]
                if check(prefix):
                    back = suffix[::-1]
                    if back != word and back in word_idx:
                        re.append([word_idx[back], i])
                # if a palindrome can be created by appending an entire other word to the current word, then we will already consider                         # such a palindrome when considering the empty string as prefix for the other word.
                if j != len(word) and check(suffix):  
                    back = prefix[::-1]
                    if back != word and back in word_idx:
                        re.append([i, word_idx[back]])
        return re