[LeetCode] Longest Palindromic Substring

Link : 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, and there exists one unique longest palindromic substring.

Analysis:

First thought is brute force. For every kind selection of start point and end point, there are totally O(N*N) and each palindrome recognition is O(N). And total time complexity is O(N^3). Test proved it's too slow.

Second try. Because Palindrome has special property, symmetric. If a long string is a Palindrome, the sub-string in its center has to be a sub-string. Or in another way, if its sub-string in the middle is not a palindrome, the large one cannot be, thus avoiding a lot of unnecessary comparison.

[LeetCode] Valid Palindrome

Link : Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. For example, "A man, a plan, a canal: Panama" is a palindrome. "race a car" is not a palindrome. Note: Have you consider that the string might be empty? This is a good question to ask during an interview. For the purpose of this problem, we define empty string as valid palindrome.