5种关于字符串中“最长”问题的解法

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

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

1. 最长公共子序列
2. 最长公共子串
3. 最长递增子序列
4. 最长公共前缀
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]结尾的序列的长度-1int[] memo = new int[num.length];for(int i = 1;inum[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#管理一枚。欢迎大家进来交流技术。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！