Given a sequence, find the length of the longest palindromic subsequence in it. For example, if the given sequence is “BBABCBCAB”, then the output should be 7 as “BABCBAB” is the longest palindromic subseuqnce in it. “BBBBB” and “BBCBB” are also palindromic subsequences of the given sequence, but not the longest ones.
// Everay single character is a palindrom of length 1 L(i, i) = 1 for all indexes i in given sequence // IF first and last characters are not same If (X[i] != X[j]) L(i, j) = max{L(i + 1, j),L(i, j - 1)} // If there are only 2 characters and both are same Else if (j == i + 1) L(i, j) = 2 // If there are more than two characters, and first and last // characters are same Else L(i, j) = L(i + 1, j - 1) + 2
Solution 1:
递归。
public int lps_recursive(String s) { return lps(s, 0, s.length()-1); } private int lps(String s, int i, int j) { if(i > j) return 0; if(i == j) return 1; if(s.charAt(i) == s.charAt(j)) { return lps(s, i+1, j-1) + 2; } else { return Math.max(lps(s, i+1, j), lps(s, i, j-1)); } }
Solution 2:
动态规划。
public int lps(String s) { int n = s.length(); // f[i][j]: longest panlindrome seq from i to j int[][] f = new int[n][n]; for(int i=0; i<n; i++) { f[i][i] = 1; } // sliding window size for(int w=2; w<=n; w++) { for(int i=0; i<=n-w; i++) { int j = i+w-1; if(s.charAt(i) == s.charAt(j)) { f[i][j] = (i+1>j-1?0:f[i+1][j-1]) + 2; } else { f[i][j] = Math.max(f[i+1][j], f[i][j-1]); } } } return f[0][n-1]; }
相关推荐
Longest Palindrome time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Returning back to problem solving, Gildong is now studying about ...
Longest Palindrome 题目 Returning back to problem solving, Gildong is now studying about palindromes. He learned that a palindrome is a string that is the same as its reverse. For example, strings ...
LMS Longest Monotonically Increasing Sequence Algorithm
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Java AC 版本
关于Longest Common Subsequences演算法
这是动态规划中,求最长公共子序列(Longest common string)的源代码。自己编写执行。程序简单,有注释。
北大POJ2533-Longest Ordered Subsequence【O(nlogn)】
Longest Ordered Subsequence,算法分析与设计,C语言程序
Longest Common Ancestor classic ppt...
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
Pku acm 第2533题 Longest Ordered Subsequence 代码,有详细的注释,动态规划
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
LCS(longest common substring)算法,即最大公共子串,它是求两个字符串最长公共子串的问题。大体解法是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长...
LeetCode Longest Common Prefix解决方案
北大POJ2533-Longest Ordered Subsequence 解题报告+AC代码
get_longest_palindrome ( string ) 返回最长的子字符串,即回文。 首先生成主字符串的所有子字符串。 我们遍历这些子字符串,并检查它是否比当前最长的子字符串长,并且是否是回文。 如果两个条件都满足,则该子...
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. ...
Estimating the Longest Increasing Subsequence in Nearly Optimal Time_在近似最优时间内估计最长增长子序列.pdf
其中在zip_longest(it_obj1, …, it_objN, fillvalue=None)时,其函数实现的功能和内置zip函数大致相同(实现一一对应), 不过内置的zip函数是已元素最少对象为基准,而zip_longest函数是已元素最多对象为基准,使用...
北大POJ2533-Longest Ordered Subsequence【O(n^2)】