每日算法 — 使用java实现诗词大会：动态规划最长公共子序列与诗词接龙匹配

引言

诗词大会是一款融合传统文化与智力竞技的趣味游戏，核心玩法之一是诗词接龙：系统给出一句诗词的上句，玩家需要快速匹配含有相同关键字或承接语义的下句。要实现一个智能的诗词接龙匹配系统，关键在于如何高效计算两句诗词之间的最长公共子序列（Longest Common Subsequence, LCS），从而量化语义关联度。本文将用Java完整实现这一核心算法，并结合Trie树实现前缀快速匹配，构建高效的诗词接龙引擎。

核心算法设计

1. 最长公共子序列（LCS）动态规划

LCS问题是经典的动态规划问题。给定两个字符串X和Y，求它们最长的公共子序列长度。定义dp[i][j]为X[0..i-1]与Y[0..j-1]的LCS长度，状态转移方程为：

• 若X[i-1] == Y[j-1]，则dp[i][j] = dp[i-1][j-1] + 1
• 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])

时间复杂度O(mn)，空间复杂度可优化至O(min(m,n))。

2. Trie树前缀匹配加速

为了快速检索以特定字开头的诗词，我们构建Trie树索引。每个节点存储一个汉字，从根到叶子的路径构成一句诗词。通过前缀遍历，可在O(k)时间内找到所有以k字开头的候选句，其中k为前缀长度。

Java实现

import java.util.*;

/**
 * 诗词大会接龙匹配系统
 * 核心算法：动态规划LCS + Trie树前缀匹配
 */
public class PoetryContest {

    // ==================== LCS动态规划核心 ====================

    /**
     * 计算两个字符串的最长公共子序列长度
     * 使用滚动数组优化空间复杂度至O(min(m,n))
     * @param s1 诗词句1
     * @param s2 诗词句2
     * @return LCS长度
     */
    public static int lcsLength(String s1, String s2) {
        if (s1 == null || s2 == null) return 0;
        // 确保s1为较短字符串，优化空间
        if (s1.length() < s2.length()) {
            String tmp = s1; s1 = s2; s2 = tmp;
        }
        int m = s1.length(), n = s2.length();
        // 仅需两行dp数组
        int[] prev = new int[n + 1];
        int[] curr = new int[n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    curr[j] = prev[j - 1] + 1;
                } else {
                    curr[j] = Math.max(prev[j], curr[j - 1]);
                }
            }
            // 交换引用，curr变为prev
            int[] swap = prev; prev = curr; curr = swap;
            Arrays.fill(curr, 0); // 清空当前行
        }
        return prev[n];
    }

    /**
     * 计算语义相似度评分（0.0 ~ 1.0）
     * 基于LCS长度与较长句长度的比值
     */
    public static double similarity(String s1, String s2) {
        if (s1 == null || s2 == null || s1.isEmpty() || s2.isEmpty()) return 0.0;
        int lcs = lcsLength(s1, s2);
        return (double) lcs / Math.max(s1.length(), s2.length());
    }

    // ==================== Trie树索引 ====================

    static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        // 存储以该节点结尾的完整诗词句
        List<String> poems = new ArrayList<>();
        boolean isEnd = false;
    }

    private final TrieNode root = new TrieNode();

    /**
     * 向Trie树插入一句诗词
     */
    public void insertPoem(String poem) {
        TrieNode node = root;
        for (char c : poem.toCharArray()) {
            node = node.children.computeIfAbsent(c, k -> new TrieNode());
        }
        node.isEnd = true;
        node.poems.add(poem);
    }

    /**
     * 前缀搜索：找到所有以prefix开头的诗词
     */
    public List<String> searchByPrefix(String prefix) {
        List<String> results = new ArrayList<>();
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            node = node.children.get(c);
            if (node == null) return results;
        }
        dfsCollect(node, results);
        return results;
    }

    private void dfsCollect(TrieNode node, List<String> results) {
        if (node.isEnd) results.addAll(node.poems);
        for (TrieNode child : node.children.values()) {
            dfsCollect(child, results);
        }
    }

    // ==================== 诗词接龙匹配引擎 ====================

    /**
     * 为给定上句寻找最佳接龙下句
     * 策略：1) 提取末尾2-3字作为Trie前缀 2) 候选句中按LCS相似度排序
     * @param upper 上句诗词
     * @param candidates 候选诗词库
     * @return 最佳匹配下句
     */
    public String findBestMatch(String upper, List<String> candidates) {
        if (upper == null || upper.isEmpty() || candidates.isEmpty()) return null;

        // 提取末尾2字作为前缀线索
        int prefixLen = Math.min(2, upper.length());
        String prefix = upper.substring(upper.length() - prefixLen);

        // 优先尝试Trie前缀匹配缩小候选集
        List<String> narrowed = searchByPrefix(prefix);
        if (narrowed.isEmpty()) narrowed = candidates;

        String best = null;
        double bestScore = -1.0;

        for (String candidate : narrowed) {
            // 跳过与上句完全相同
            if (candidate.equals(upper)) continue;

            // 计算LCS相似度
            double sim = similarity(upper, candidate);

            // 额外奖励：候选句首字与上句尾字相同（传统接龙规则）
            char lastChar = upper.charAt(upper.length() - 1);
            char firstChar = candidate.charAt(0);
            if (lastChar == firstChar) sim += 0.15;

            if (sim > bestScore) {
                bestScore = sim;
                best = candidate;
            }
        }
        return best;
    }

    // ==================== 主程序与测试 ====================

    public static void main(String[] args) {
        PoetryContest engine = new PoetryContest();

        // 构建诗词库
        String[] poems = {
            "白日依山尽",
            "黄河入海流",
            "欲穷千里目",
            "更上一层楼",
            "春眠不觉晓",
            "处处闻啼鸟",
            "夜来风雨声",
            "花落知多少",
            "床前明月光",
            "疑是地上霜",
            "举头望明月",
            "低头思故乡"
        };

        for (String p : poems) engine.insertPoem(p);

        System.out.println("===== 诗词大会接龙匹配系统 =====\n");

        // 测试LCS
        String s1 = "白日依山尽";
        String s2 = "黄河入海流";
        System.out.println("LCS(\"" + s1 + "\", \"" + s2 + "\") = " + lcsLength(s1, s2));

        String s3 = "床前明月光";
        String s4 = "举头望明月";
        System.out.println("LCS(\"" + s3 + "\", \"" + s4 + "\") = " + lcsLength(s3, s4));

        System.out.println();

        // 测试接龙匹配
        String[] uppers = {"白日依山尽", "春眠不觉晓", "床前明月光"};
        for (String upper : uppers) {
            String match = engine.findBestMatch(upper, Arrays.asList(poems));
            System.out.println("上句: \"" + upper + "\" -> 最佳接龙: \"" + match + "\"");
        }

        System.out.println("\n===== Trie前缀搜索测试 =====");
        List<String> matches = engine.searchByPrefix("明");
        System.out.println("前缀\"明\"匹配结果: " + matches);
    }
}

复杂度分析

算法扩展思路

1. 加权LCS：为不同汉字赋予语义权重（如虚词权重低、实词权重高），使匹配更贴近诗词意境。
2. N-gram扩展：将诗词切分为双字或三字N-gram，通过Jaccard相似度补充LCS的不足。
3. 并行匹配：对于大规模诗词库，可将候选集按首字分桶，使用多线程并行计算LCS。

总结

本文通过动态规划求解最长公共子序列，量化了诗词句之间的语义关联，并结合Trie树实现了前缀快速索引，构建了一个高效的诗词接龙匹配引擎。代码采用滚动数组将LCS空间复杂度降至线性，Trie树保证前缀检索的高效性，整体方案适用于万级诗词库的实时接龙匹配场景。