LeetCode 524 通过删除字母匹配到字典里最长单词

🔍 从字符串中找出最长可生成子序列单词：双指针与优先级筛选（Java 实现）

🌈 一、问题描述

🎯 核心任务

给定字符串 s 和单词列表 dictionary，找出列表中最长的单词，该单词可通过删除 s 中的某些字符（不改变顺序）得到。

• 优先级：长度优先 → 字母序最小（长度相同）
• 返回：符合条件的单词（无则返回 ""）

📝 约束条件

• 时间复杂度：O (n*m)（n = 字典长度，m=s 长度）
• 空间复杂度：O (1)（仅常数额外空间）

🌰 示例

⚡ 二、解决方案：双指针 + 优先级筛选法

🔮 核心原理

1. 子序列判断（双指针法）：
   • 用两个指针遍历单词和字符串，匹配则同步移动，否则仅移动字符串指针。
2. 优先级筛选：
   • 长度优先：保留更长单词
   • 字母序次之：String.compareTo() 实现字典序比较

🚀 算法步骤（三步法）

1. 遍历字典：对每个单词执行子序列检查。
2. 子序列判断：双指针法验证是否为 s 的子序列。
3. 优先级更新：根据长度和字母序更新最优解。

🧩 三、代码实现（Java）

import java.util.List;

class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        String result = ""; // 初始最优解
        for (String word : dictionary) { // 遍历每个单词
            if (isSubsequence(word, s)) { // 检查是否为子序列
                // 优先级比较：长度 > 字母序
                if (word.length() > result.length() || 
                    (word.length() == result.length() && word.compareTo(result) < 0)) {
                    result = word; // 更新最优解
                }
            }
        }
        return result; // 返回最终结果
    }

    private boolean isSubsequence(String word, String s) {
        int i = 0, j = 0; // 双指针：i→word，j→s
        while (i < word.length() && j < s.length()) {
            if (word.charAt(i) == s.charAt(j)) { // 字符匹配
                i++; // 移动单词指针
            }
            j++; // 始终移动字符串指针
        }
        return i == word.length(); // 单词遍历完成 → 是子序列
    }
}

📊 四、复杂度分析

🔍 五、代码逐行解析（以示例 s="abpcplea", dictionary=["apple"] 为例）

1. 子序列判断：
   • word="apple"，s="a b p c p l e a"
   • 指针移动：

     i=0 (a) vs j=0 (a) → 匹配，i=1, j=1  
     i=1 (p) vs j=1 (b) → 不匹配，j=2 (p) → 匹配，i=2, j=3  
     i=2 (p) vs j=3 (c) → 不匹配，j=4 (p) → 匹配，i=3, j=5  
     i=3 (l) vs j=5 (l) → 匹配，i=4, j=6  
     i=4 (e) vs j=6 (e) → 匹配，i=5（完成）→ 返回 true  
     

2. 优先级比较：
   • 初始 result=""（长度 0）→ "apple" 长度 5 → 更新。

🧪 六、测试用例

💡 七、扩展思考

🔀 变种问题：最短子序列

• 问题：找最短的有效单词（长度优先降序）。
• 解法：修改优先级为长度升序，字母序升序。

🚀 优化策略

1. 预处理字典：按长度降序 + 字母序升序排序，找到第一个有效单词后提前终止。

   dictionary.sort((a, b) -> {
       if (a.length() != b.length()) return b.length() - a.length(); // 长度降序
       else return a.compareTo(b); // 字母序升序
   });
   

2. 剪枝优化：遍历字典时，若当前单词长度小于最优解长度，跳过。

👥 类似题目

• LeetCode 392. 判断子序列（判断是否为子序列）
• LeetCode 792. 匹配子序列的单词数（统计子序列数量）

🔄 八、两种方法对比（双指针法 vs 动态规划法）

🎨 九、可视化流程图

遍历字典每个单词 → 双指针检查子序列  
↓  
是子序列 → 比较长度和字母序 → 更新最优解  
↓  
返回最优解（或""）

🌟 十、总结：子序列问题的通用解法

✨ 核心优势

• 时空平衡：线性时间复杂度，常数空间，适合大规模数据。
• 逻辑简洁：双指针法直观易懂，避免复杂数据结构。

🚦 适用场景

• 文本匹配（如日志分析、关键词提取）
• 字符串编辑（删除字符生成目标单词）
• 数据校验（验证输入格式合法性）

💡 编程启示

1. 双指针技巧：处理子序列问题的标配，通过同步遍历实现线性时间判断。
2. 优先级设计：明确比较规则（长度→字母序），利用字符串内置方法（compareTo）简化实现。

📚 十一、延伸阅读

• 子序列定义：维基百科 - 子序列
• 字符串比较：Java String.compareTo () 详解
• 
   

🎁 最后的话

这道题教会我们如何用双指针的 “舞蹈” 优雅地检查子序列，同时用优先级规则筛选最优解。就像整理书架：先按高度（长度）排序，再按书名（字母序）排列，最终找到最合适的 “那本书”。

下次遇到字符串匹配问题时，记住双指针的魔力：让字符在遍历中自然匹配，让优先级在比较中浮出水面。代码的简洁，正是算法之美的最佳注脚！ 📜✨