leetcode/palindromic_substring
palindromic_substring
dz /
leetcode /
palindromic_substring
Summary
Given a string s, return the longest palindromic substring in s.
Node Tree
Nodes
intuition_pre_hint
|
content
|
The brute-force approach I imagine would involve taking each character, and then sweeping backwards from the end of string, check every matching character to see if the region marks a palindrome. Palindromes can be split in half, which means the largest segment a palindrome can be is N/2. There might be a way to use this property to make a more efficient algorithm, perhaps a sliding window. Another approach: finding potential palindromes starting at the center, and working backwards. The smallest possible even palindrome is two duplicate letters. The smallest possible odd palindrome is 3 letters (not counting 1 letter), with a center letter and two duplicate letters on the outside. You could do a linear sweep for even/odd palindromes, and upon finding one, expand the palindrome out on either end and check the size.
|
children
|
expand_from_centers (thought about this here), intuition_post_hint (after reading the hint), brute_force
|
remarks
|
There's a hint on the leetcode website that I'm ignoring for the moment. So my thoughts here are just reading the problem.
|
intuition_post_hint
|
content
|
The language of the 3 uses terms like "re-use previously computed palindrome", which suggests a solution using recursion and/or dynamic programming. My initial thoughts finding palindrome centers seems close. Apparently the O(n) palindrome checks in brute force can be reduced to O(1). So, that seems like a data structure.
|
children
|
dynamic_programming (what I thought of after reading the hints)
|
parents
|
intuition_pre_hint
|
remarks
|
thoughts after reading the hint
|
use_of_matrix_structure
|
content
|
Use of matrix data structure. Still trying to grok this, though the comments are helpful. I should have read the constraints of the string length (max length 1000), that would have been a good hint.
|
children
|
error_in_comments (reading comments about matrix)
|
parents
|
cpp_implementation
|
dynamic_programming
|
content
|
The dynamic programming algorithm is basically what the C++ solution was attempting to do. The LC algorithm uses a boolean table, while the C++ solution I think keeps track of the sizes? The answer they come to is incorrect when they work it out in the comments, so I'm mildly skeptical this is a correct algorithm.
|
parents
|
leetcode_editorial, intuition_post_hint, cpp_implementation
|