最长公共子序列（Java）

2023-07-23 15:51| 来源: 网络整理| 查看: 265

最长公共子序列运用十分广泛，例如人脸识别，相似度比较等方面。子序列表示原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。比如：“abc”，“ac”是子序列，但“ca”不是实现代码：

/** * 最长公共子序列 * * @param a * @param b */ public int longestCommonSubsequence(String a, String b) { // a b c b a // b 0 1 1 1 1 // c 0 1 2 2 2 // a 1 1 2 2 3 int[][] dp = new int[b.length() + 1][a.length() + 1];//加一行一列处理方便 for (int i = 0; i < b.length(); i++) {//遍历行 char col = b.charAt(i); for (int j = 0; j < a.length(); j++) {//遍历列 char row = a.charAt(j); if (col == row) {//行的字符等于列的字符 //当前的最长子序列长度 = 当前位置左上角的值 + 1 dp[i + 1][j + 1] = dp[i][j] + 1; } else {//不相等，取上面和左边两个值的最大值 dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]); } } } for (int i = 1; i < b.length() + 1; i++) { for (int j = 1; j < a.length() + 1; j++) { System.out.print(dp[i][j] + " "); } System.out.println(); } return dp[b.length()][a.length()]; }

测试代码：

System.out.println(longestCommonSubsequence("abcba", "bca"));

结果： 0 1 1 1 1 0 1 2 2 2 1 1 2 2 3 3

【本文地址】

公司简介

联系我们