Java如何高效查找两个用户点击URI序列中最长的匹配时序子序列

首先明确需求：我们要找的是两个点击序列中连续出现、时序一致的最长公共子串，而非允许元素间隔的最长公共子序列(LCS)，从示例可验证：User1和User2的非连续LCS长度为4（/green、/pink、/orange、/gray），但连续公共子串最长为3，和示例输出一致。

方案选型 #

• 暴力解法时间复杂度为O(m²n)，序列长度较大时性能极差，不推荐使用
• 动态规划解法时间复杂度为O(mn)，空间可优化到O(min(m,n))，是生产环境首选的高效方案

动态规划实现思路 #

定义状态dp[i][j]表示以第一个序列第i个元素、第二个序列第j个元素结尾的最长公共连续子串长度：

• 若arr1[i] == arr2[j]，则dp[i][j] = dp[i-1][j-1] + 1
• 若不相等，则dp[i][j] = 0
  遍历过程中记录最长子串的长度和结束位置，最后按位置截取即可得到结果。

Java代码实现 #

注：原示例中方法入参标注为String属于笔误，实际应该传入有序的点击序列集合：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MaxHitClickFinder {
    // 优化空间版本，空间复杂度O(min(m,n))
    public static List<String> findMaxHitClick(List<String> user1Clicks, List<String> user2Clicks) {
        // 交换长短序列，保证dp数组维度为较短序列长度，进一步节省空间
        if (user1Clicks.size() > user2Clicks.size()) {
            List<String> temp = user1Clicks;
            user1Clicks = user2Clicks;
            user2Clicks = temp;
        }
        int m = user1Clicks.size();
        int n = user2Clicks.size();
        int[] dp = new int[m + 1];
        int maxLen = 0;
        int endIndex = 0;

        for (int j = 1; j <= n; j++) {
            // 倒序遍历避免覆盖需要的dp[i-1]历史值
            for (int i = m; i >= 1; i--) {
                if (user1Clicks.get(i - 1).equals(user2Clicks.get(j - 1))) {
                    dp[i] = dp[i - 1] + 1;
                    if (dp[i] > maxLen) {
                        maxLen = dp[i];
                        endIndex = i - 1;
                    }
                } else {
                    dp[i] = 0;
                }
            }
        }

        // 截取最长公共连续子串
        List<String> result = new ArrayList<>();
        for (int i = endIndex - maxLen + 1; i <= endIndex; i++) {
            result.add(user1Clicks.get(i));
        }
        return result;
    }

    public static void main(String[] args) {
        // 场景1测试
        List<String> user1 = Arrays.asList("/blue", "/green", "/pink", "/orange", "/white", "/gray");
        List<String> user2 = Arrays.asList("/brown", "/green", "/pink", "/orange", "/red", "/gray");
        System.out.println(findMaxHitClick(user1, user2)); // 输出 [/green, /pink, /orange]

        // 场景2测试
        List<String> user3 = Arrays.asList("/blue", "/green", "/pink");
        List<String> user4 = Arrays.asList("/blue");
        System.out.println(findMaxHitClick(user3, user4)); // 输出 [/blue]
    }
}

优化点说明 #

• 交换长短序列，保证dp数组长度始终为较短序列的长度，最大程度降低空间占用
• 用一维数组代替二维数组，倒序遍历避免覆盖上一轮的计算值，空间复杂度从O(mn)降到O(min(m,n))
• 仅记录最大长度和结束位置，无需存储所有中间子串，运行时内存占用更低

内容的提问来源于stack exchange，提问作者user1591156