字串"/>
输出最长公共字串
题目描述
给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列
示例
示例 1:
输入:text1 = "abcde", text2 = "ace"
输出:"ace"
示例 2:
输入:text1 = "abc", text2 = "abc"
输出:"abc"
示例 3:
输入:text1 = "abc", text2 = "def"
输出:""
思路
本质之前写过的最长公共子序列一样,先求出最长公共子序列的长度,然后根据长度在遍历两个字符串,组成真正的最长公共子序列。
代码如下
public String longestCommonSubsequenceToString(String text1, String text2) {int m = text1.length(), n = text2.length();int[][] dp = new int[m + 1][n + 1];// 统计最长公共子序列for(int i = 1;i < dp.length;i++){for(int j = 1;j < dp[0].length;j++){if(text1.charAt(i - 1) == text2.charAt(j - 1)){dp[i][j] = 1 + dp[i - 1][j - 1];}else{dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);}}}// 记录最长公共子序列长度,int len = dp[m][n];char[] chars = new char[len];// 其实这里也不必定义char数组和记录最长公共子序列长度,直接使用StringBuilder来操作更简单,最后返回结果在reverse()一下就行。int i = m, j = n;// 从后向前遍历两个字符串while(i > 0 && j > 0){// 相等就加入if(text1.charAt(i - 1) == text2.charAt(j - 1)){chars[len - 1] = text1.charAt(i - 1);i--;j--;len--;}else if(dp[i - 1][j] > dp[i][j - 1]){i--;}else{j--;}}return new String(chars);}
更多推荐
输出最长公共字串
发布评论