Given a string, determine if a permutation of the string could form a palindrome. Example 1 Input: "code" Output: false Example 2 Input: "aab" Output: true Example 3 Input: "carerac" Output: true Solution class Solution: def canPermutePalindrome(self, s: str) -> bool: lookup = set() for c in s: if c not in lookup: lookup.add(c) else: lookup.remove(c) return len(lookup) <= 1
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" Solution Dynamic Programming # https://leetcode.com/problems/longest-palindromic-substring/discuss/157861/Python3-DP-Solution-with-Lots-of-Comments # time: O(n^2) # space: O(n^2) class Solution(object): def longestPalindrome(self, s): """ :type s: str :rtype: str """ str_len = len(s) if str_len == 0: return "" # Initialize DP table (dimensions: str_len x str_len) memo = [[False for i in range(str_len)] for j in range(str_len)] start = 0 # Starting index of the longest palindrome max_len = 1 # Length of the longest palindrome # Fill DP table for single char palindromes for i in range(str_len): memo[i][i] = True # Fill DP table for 2 char long palindromes for i in range(str_len - 1): j = i + 1 if s[i] == s[j]: memo[i][j] = True start = i max_len = 2 # Fill DP table for palindromes of every other length # starting from 3 for length in range(3, str_len + 1): for i in range(str_len - length + 1): j = i + (length - 1) if s[i] == s[j] and memo[i+1][j-1]: memo[i][j] = True start = i max_len = length return s[start: start + max_len] # time: O(n^2) # space: O(1) class Solution(object): def __init__(self): self.
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. Note: For the purpose of this problem, we define empty string as valid palindrome. Example 1 Input: "A man, a plan, a canal: Panama" Output: true Example 2 Input: "race a car" Output: false Solution class Solution: def isPalindrome(self, s): """ :type s: str :rtype: bool """ if not s: return True head = 0 tail = len(s) - 1 while head <= tail: cHead, cTail = s[head], s[tail] if not cHead.