Analysis: Dynamic Programming
To improve over the brute force solution, we first observe how we can avoid unnecessary re-computation while validating palindromes.
Consider the case
"ababa"
. If we already knew that"bab"
is a palindrome, it is obvious that"ababa"
must be a palindrome since the two left and right end letters are the same.
Define $P(i,j)$ as following:
$$ \begin{equation} P(i, j)=\left{ \begin{array}{lr} \text{true,}&\quad\text{if the substring } S_i \dots S_j \text{ is a palindrome} \ \text{false,} &\quad\text{otherwise.} \end{array} \right. \end{equation} $$
Therefore,
$$P(i,j)=(P(i+1,j−1) \land S_i==S_j)$$
The base cases are:
$$P(i, i) = true$$
$$P(i, i+1) = (S_i == S_{i+1})$$
Complexity Analysis
- Time complexity : $O(n^2)$. This gives us a runtime complexity of $O(n^2)$.
- Space complexity : $O(n^2)$. It uses $O(n^2)$ space to store the table.
[scode type="yellow"]
- 这道题中由动态规划的递推公式可知,在矩阵中,当前位置由其右下角的单元及字符串本身决定。
- 因此在自底向顶的设计中,应该优先填充左下角的部分
- i--
- j++ 其中 i 表示横,j 表示纵 [/scode]
My solution: 38ms
|
|