（尊重劳动成果，转载请注明出处：http://blog.csdn.net/qq_25827845/article/details/77725795冷血之心的博客）

常见的5种关于字符串中“最长”问题：

最长公共子序列最长公共子串最长递增子序列最长公共前缀最长不含重复元素的子串

最长公共子序列

子序列不需要连续，给定两个不同长度的字符串，如何求出最长公共子序列？

递归解法：

/** * 最长公共子序列，返回值为长度 * @param x * @param y * @return */ int longestPublicSubSequence(String x, String y){ if(x.length() == 0 || y.length() == 0){ return 0; } if(x.charAt(0) == y.charAt(0)){ return 1 + longestPublicSubSequence(x.substring(1), y.substring(1)); }else{ return Math.max(longestPublicSubSequence(x.substring(1), y.substring(0)), longestPublicSubSequence(x.substring(0), y.substring(1))); } }

非递归解法：

int getLCS(String str, String str2){ int n1 = str.length(); int n2 = str2.length(); int[][] dp = new int[n1+1][n2+1]; for(int i=1;i<=n1;i++){ for(int j=1;j<=n2;j++){ if(str.charAt(i-1)==str2.charAt(j-1)){ //此处应该减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[n1][n2]; }

画图分析，最长公共子序列：

若对应位置字符相等，则可以这样表示：

反之，若不相等，则表示如下：

递归个非递归的区别是，非递归方法中将结果保存在数组中。  

最长公共子串

/** * 最长公共子串 * @param str1 * @param str2 * @return */ int longestPublicSubstring(String str1, String str2){ int l1 = str1.length(); int l2 = str2.length(); int[][] val = new int[l1][l2]; for(int i = 0; i < l1; i++){ for(int j = 0; j < l2; j++){ if(str1.charAt(i) == str2.charAt(j)){ if(i >= 1 && j >= 1){ val[i][j] = val[i - 1][j - 1] + 1; }else{ val[i][j] = 1; } }else{ val[i][j] = 0; } } } // 找到val数组中的最大值 int max = 0; for(int i = 0; i < l1; i++){ for(int j = 0; j < l2; j++){ max = Math.max(val[i][j], max); } } return max; }

画图分析：

 

最长递增子序列

这是一道典型的动态规划试题。使用memo[ ]数组保存中间结果

/** * 最长递增子序列 动态规划 * @param num * @return */ public static int LongestLIS(int[] num){ if(num.length<1) return 0; // 定义一个memo数组memo[i]表示以num[i]结尾的序列的长度-1 int[] memo = new int[num.length]; for(int i = 1;i<num.length;i++){ for(int j = 0;j<i;j++){ if(num[i]>num[j]){ memo[i] = Math.max(memo[i], 1+memo[j]); } } } // 遍历memo数组，找到最大值，并且返回max+1; int max = 0; for (int i = 0; i < memo.length; i++) { max = Math.max(max, memo[i]); } return max+1; }

最长公共前缀

/* * 求一个字符串数组的最长公共前缀 * Write a function to find the longest common prefix string amongst an array of strings. */ public class Main { public static void main(String[] args) { String[] s = {"acvxx","axc","aaa"}; System.out.println(longestCommonPrefix(s)); } public static String longestCommonPrefix(String[] strs) { if(strs == null || strs.length == 0) return ""; String pre = strs[0]; int i = 1; while(i < strs.length){ while(strs[i].indexOf(pre) != 0) // 字符串String的indexOf方法使用 pre = pre.substring(0,pre.length()-1); i++; } return pre; } }

该方法巧妙之处就是充分利用了indexOf( )方法，先将数组中的第一个元素作为最长前缀，然后向后遍历数组，判断是否是后边字符串的前缀，若不是，则从后边减小该前缀，直到最后前缀为“”。

最长不含重复元素的子串

本题详见本人博客：

LeetCode 题解 3. Longest Substring Without Repeating Characters（最长不含重复字符的子字符串）

 

如果对你有帮助，记得点赞哦~欢迎大家关注我的博客，可以进群366533258一起交流学习哦~

本群给大家提供一个学习交流的平台，内设菜鸟Java管理员一枚、精通算法的金牌讲师一枚、Android管理员一枚、蓝牙BlueTooth管理员一枚、Web前端管理一枚以及C#管理一枚。欢迎大家进来交流技术。