Problem statement:
Given a string S, find the longest palindromic substring in S.
Substring of string S:
S[i...j] where 0 <= i <= j < len(S)
Palindrome string:
A string which reads the same backwards. More formally, S is palindrome if
reverse(S) = S.
Incase of conflict, return the substring which occurs first ( with the least starting index ).
Example :
Input : "aaaabaaa"
Output : "aaabaaa"
Plan to work on java coding in short future.
Hint:
Brute force:
How many substrings? - start position and end position, O(N^2) variables, and each substring needs one palindrome check, so time complexity is O(N^3).
Facebook code lab editorial hint:
Brute force:
How many substrings? - start position and end position, O(N^2) variables, and each substring needs one palindrome check, so time complexity is O(N^3).
Facebook code lab editorial hint:
A simpler approach, O(N^2) time and O(1) space:
In fact, we could solve it in O(N^2) time without any extra space.
We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2N-1 such centers.
You might be asking why there are 2N-1 but not N centers?
The reason is that the center of a palindrome can be in between two letters.
Such palindromes have even number of letters (such as “abba”) and their center are between the two ‘b’s.
Since expanding a palindrome around its center could take O(N) time, the overall complexity is O(N^2).
highlights:
1. String - compile error: string, Java String class, not string. Different from C#
2. String.substring(int beginIndex, endIndex), endIndex is exclusive <- understand exclusive meaning here: line 66, line 90
3. Java String [] operator - compiler error, using charAt() function
4 . line 33 - 36 bug removal - use extra boolean update, since line 35 - update maxLength, so line 36 update boolean shouldnot be used. Saved status
5. Two for loops can be merged into one loop
6. Design concern, use start pos and end pos, substring has O(n^2), but if only consider the center position of palindrome, only O(n) case.
2. String.substring(int beginIndex, endIndex), endIndex is exclusive <- understand exclusive meaning here: line 66, line 90
3. Java String [] operator - compiler error, using charAt() function
4 . line 33 - 36 bug removal - use extra boolean update, since line 35 - update maxLength, so line 36 update boolean should
5. Two for loops can be merged into one loop
6. Design concern, use start pos and end pos, substring has O(n^2), but if only consider the center position of palindrome, only O(n) case.
Blogs to read:
Excellent analysis - brute force O(n^4) -> O(n^3)
No comments:
Post a Comment