Chapter 49 Linkedin 2015
49.1 Longest Palindromic Subsequence
OJ: https://www.hackerrank.com/challenges/longest-palindromic-subsequence
http://users.eecs.northwestern.edu/~dda902/336/hw6-sol.pdf
http://www.1point3acres.com/bbs/thread-140246-1-1.html
T: \(O(N^2)\)
http://www.geeksforgeeks.org/dynamic-programming-set-12-longest-palindromic-subsequence/
如果光是求长度的话,用迭代,这代码出奇的简单:
int LPS_len(string& s, int head, int tail){
if(head==tail) return 1; // one char
if(head+1==tail) return (s[head]==s[tail])?2:1; // two chars
if(s[head]==s[tail]) return LPS_Len(s,head+1,tail-1)+2;
return max(LPS_Len(s,head,tail-1),LPS_Len(s,head+1,tail));
}用递归复杂度还不容易看出来.其实是Complexity: T:\(O(N^2)\) S: no extra space
用迭代法就容易看出来了.
49.1.1 5. Longest Palindromic Substring
https://leetcode.com/problems/longest-palindromic-substring/
49.3 Identical BST
http://algorithms.tutorialhorizon.com/check-if-two-bsts-are-identical/
The same as Same Tree problem
