In the bottom-up approach, why does the DP table store boolean values instead of current palindrome substring length? Isn’t it important for the DP table to store the current count for each subproblem? Also, a current length of 0 would easily tell us that a subproblem isn’t a palindromic substring.
Course: Grokking Dynamic Programming Patterns for Coding Interviews - Learn Interactively
Lesson: Longest Palindromic Substring - Grokking Dynamic Programming Patterns for Coding Interviews
Hello @Vrdko93,
The approach used in this lesson is used for different purposes including the Longest Common sequence. While it is true that the longest palindromic substring can be found with a more efficient algorithm, it would seem that the author has decided to use the dynamic approach for this problem as well. As for your last remark, what do you mean the current length of 0 would solve the problem because the substring can exist at any part of the string, so all of it does need to be matched? Hope this answers your query, but if I misunderstood your concerns, please do ask again, and I will be happy to answer.
What I meant was, why not use a DP table of type “int” instead of a DP table of type “boolean”?
Course: https://www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews
Lesson: Longest Palindromic Substring - Grokking Dynamic Programming Patterns for Coding Interviews