LIS 和 LCS 子序列子串问题

1. Longest Common Substring 和 Longest Common Subsequences"abcdefg" : 子序列是可以不连续的 eg:"acg", 子串是必须连续的eg:"abc".1) LC子序列(子序列是看某点(可不选)之前能组成的所有)public int longestCommonSubsequence(String A, String B) { // write your code here if(A == null || A.length() == 0 || B == null || B.length() == 0) return 0; int m = A.length(), n = B.length(); int[][] dp = new int[m+1][n+1]; for(int i = 1; i <= m; i++) { for(int j = 1; j <= n; j++) { if(A.charAt(i-1) == B.charAt(j-1)) { dp[i][j] = dp[i-1][j-1] + 1; }else{ dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); } } } return dp[m][n]; }2) LC子串 substring (子串是看以某两个点(必选)结尾的substring)public int longestCommonSubstring(String A, String B) { // write your code here if(A == null || B == null || A.length() == 0 || B.length() == 0) return 0; int m = A.length(), n = B.length(); int[][] dp = new int[m+1][n+1]; int max = 0; for(int i = 1; i <= m; i++) { for(int j = 1; j <= n; j++) { if(A.charAt(i-1) == B.charAt(j-1)) { dp[i][j] = dp[i-1][j-1] + 1; max = Math.max(dp[i][j], max); } } } return max; }###2. Longest Increasing Subsequences (最长上升子序列，有O(n^2) 和 O(nlgn) 两种解法)1) O(n^2) 解法DPpublic int lengthOfLIS(int[] nums) { //0(n^2) dp //以某点为结尾的最长lis，等于它之前所有小于它的lis的最大值+1 if(nums == null || nums.length == 0) return 0; int[] dp = new int[nums.length]; dp[0] = 1; int max = 1; for(int i = 1; i < nums.length; i++) { dp[i] = 1; for(int j = 0; j < i; j++) { if(nums[j] < nums[i]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } max = Math.max(dp[i], max); } return max; }2) O(nlgn) 解法 binary searchpublic int lengthOfLIS(int[] nums) { //O(nlgn) binary search if(nums == null || nums.length == 0) return 0; int[] res = new int[nums.length]; Arrays.fill(res, Integer.MAX_VALUE); for(int i = 0; i < nums.length; i++) { int index = binarySearch(res, nums[i]); res[index] = nums[i]; } for(int i = res.length - 1; i >= 0; i--) { if(res[i] != Integer.MAX_VALUE) return i + 1; } return 1; } public int binarySearch(int[] arr, int num) { int left = 0, right = arr.length-1; while(left + 1 < right) { int mid = left + (right - left)/2; if(arr[mid] >= num) right = mid; else left = mid; } if(arr[left] >= num) return left; return right; }###3. Longest Palindromic SubString 和 Subsequences1) SubString 连续的Example:Input: "babad"Output: "bab"Note: "aba" is also a valid answer.``````public class Solution { int left = -1; int len = 0; public String longestPalindrome(String s) { if(s == null || s.length() == 0) return ""; for(int i = 0; i < s.length(); i++) { expand(s, i, i); expand(s, i, i+1); } return s.substring(left, left + len); } public void expand(String s, int i, int j) { while(i >= 0 && i < s.length() && j >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) { i--; j++; } if(j - i - 1 > len) { len = j - i - 1; left = i + 1; } }}2) subsequencespublic class Solution { public int longestPalindromeSubseq(String s) { if(s == null || s.length() == 0) return 0; int[][] dp = new int[s.length()][s.length()]; for(int i = s.length()-1; i >= 0; i--) { dp[i][i] = 1; for(int j = i + 1; j < s.length(); j++) { if(s.charAt(i) == s.charAt(j)) { dp[i][j] = dp[i+1][j-1] + 2; //"aa" --> dp[0][1] = dp[1][0] + 2; dp[1][0] 左大于右了，是=0的 }else{ dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]); } } } return dp[0][s.length()-1]; }}