连云港市千栀味食品贸易有限公司
User Avatar

专业网站建设黄冈网站建设

连云港市千栀味食品贸易有限公司 2026/09/09 18:05:00

匹配子序列的单词数

问题描述

给定字符串s和一个字符串数组words，返回words中是s的子序列的单词数目。

子序列：通过删除s中的一些字符（也可以不删除）而不改变剩余字符相对位置所形成的新字符串。

示例：

输入: s = "abcde", words = ["a","bb","acd","ace"] 输出: 3 解释: 有三个单词是s的子序列："a"，"acd"，"ace"。

算法思路

暴力：

  • 对每个单词都从头开始在s中匹配
  • 时间复杂度：O(words.length × s.length × avg_word_length)
  • 对于大量重复单词会重复计算

方法：

  1. 预处理 + 二分查找：为每个字符预处理其在s中的位置，然后对每个单词使用二分查找
  2. 多指针：为每个单词维护一个指针，同时遍历s
  3. 缓存：使用哈希表缓存已计算的结果，避免重复单词的重复计算

代码实现

方法一：预处理 + 二分查找

importjava.util.*;classSolution{/** * 使用预处理和二分查找判断子序列 * * @param s 源字符串 * @param words 单词数组 * @return 是s的子序列的单词数目 */publicintnumMatchingSubseq(Strings,String[]words){// 1: 预处理 - 为每个字符记录其在s中出现的所有位置List<Integer>[]positions=newList[26];for(inti=0;i<26;i++){positions[i]=newArrayList<>();}for(inti=0;i<s.length();i++){positions[s.charAt(i)-'a'].add(i);}// 2: 使用缓存避免重复计算Map<String,Boolean>cache=newHashMap<>();intcount=0;// 3: 对每个单词判断是否为子序列for(Stringword:words){if(cache.containsKey(word)){if(cache.get(word)){count++;}continue;}booleanisSubseq=isSubsequence(word,positions);cache.put(word,isSubseq);if(isSubseq){count++;}}returncount;}/** * 使用二分查找判断单词是否为子序列 * * @param word 待检查的单词 * @param positions 字符位置预处理数组 * @return true表示是子序列，false表示不是 */privatebooleanisSubsequence(Stringword,List<Integer>[]positions){intprevIndex=-1;// 上一个匹配字符在s中的位置for(charc:word.toCharArray()){List<Integer>charPositions=positions[c-'a'];// 如果字符c在s中不存在，直接返回falseif(charPositions.isEmpty()){returnfalse;}// 二分查找第一个大于prevIndex的位置intleft=0,right=charPositions.size();while(left<right){intmid=left+(right-left)/2;if(charPositions.get(mid)<=prevIndex){left=mid+1;}else{right=mid;}}// 如果没有找到合适的位置if(left==charPositions.size()){returnfalse;}// 更新prevIndex为找到的位置prevIndex=charPositions.get(left);}returntrue;}}

方法二：多指针

importjava.util.*;classSolution{/** * 使用多指针判断子序列 * 为每个单词维护一个指针，同时遍历s */publicintnumMatchingSubseq(Strings,String[]words){// 使用缓存避免重复计算Map<String,Integer>wordCount=newHashMap<>();for(Stringword:words){wordCount.put(word,wordCount.getOrDefault(word,0)+1);}// 为每个唯一单词创建指针Map<String,Integer>pointers=newHashMap<>();for(Stringword:wordCount.keySet()){pointers.put(word,0);}intmatchedCount=0;// 遍历s的每个字符for(charc:s.toCharArray()){// 复制需要更新的单词列表List<String>toRemove=newArrayList<>();// 检查每个单词的当前指针位置for(Stringword:pointers.keySet()){intptr=pointers.get(word);if(ptr<word.length()&&word.charAt(ptr)==c){ptr++;pointers.put(word,ptr);// 如果单词完全匹配if(ptr==word.length()){matchedCount+=wordCount.get(word);toRemove.add(word);}}}// 移除已完全匹配的单词for(Stringword:toRemove){pointers.remove(word);}}returnmatchedCount;}}

方法三：优化二分查找

importjava.util.*;classSolution{/** * 使用Collections.binarySearch优化的二分查找 */publicintnumMatchingSubseq(Strings,String[]words){// 预处理字符位置List<Integer>[]positions=newList[26];for(inti=0;i<26;i++){positions[i]=newArrayList<>();}for(inti=0;i<s.length();i++){positions[s.charAt(i)-'a'].add(i);}Map<String,Boolean>cache=newHashMap<>();intcount=0;for(Stringword:words){if(cache.computeIfAbsent(word,w->isSubsequenceOptimized(w,positions))){count++;}}returncount;}privatebooleanisSubsequenceOptimized(Stringword,List<Integer>[]positions){intprevIndex=-1;for(charc:word.toCharArray()){List<Integer>list=positions[c-'a'];if(list.isEmpty())returnfalse;// 使用Collections.binarySearch找到插入位置intpos=Collections.binarySearch(list,prevIndex+1);if(pos<0){pos=-pos-1;// 转换为插入位置}if(pos>=list.size()){returnfalse;}prevIndex=list.get(pos);}returntrue;}}

方法四：暴力

importjava.util.*;classSolution{/** * 暴力双指针，使用缓存优化 */publicintnumMatchingSubseq(Strings,String[]words){Map<String,Boolean>cache=newHashMap<>();intcount=0;for(Stringword:words){if(cache.computeIfAbsent(word,w->isSubsequenceBrute(s,w))){count++;}}returncount;}privatebooleanisSubsequenceBrute(Strings,Stringword){inti=0,j=0;while(i<s.length()&&j<word.length()){if(s.charAt(i)==word.charAt(j)){j++;}i++;}returnj==word.length();}}

算法分析

  • 时间复杂度：

    • 预处理 + 二分查找：O(s.length + (word.length × log(s.length)))
    • 多指针：O(s.length × unique_words_count)
    • 暴力（带缓存）：O(s.length × unique_words_count)

  • 空间复杂度：

    • 预处理 + 二分查找：O(s.length + unique_words_count)
    • 多指针：O(unique_words_count × avg_word_length)
    • 暴力：O(unique_words_count × avg_word_length)

算法过程

1：s = “abcde”, words = [“a”,“bb”,“acd”,“ace”]

预处理：

  • positions[‘a’] = [0]
  • positions[‘b’] = [1]
  • positions[‘c’] = [2]
  • positions[‘d’] = [3]
  • positions[‘e’] = [4]

单词检查：

  1. “a”：

    • 字符’a’：在positions[0]中找> -1的位置 → 找到0
    • 完全匹配

  2. “bb”：

    • 第一个’b’：在positions[1]中找> -1的位置 → 找到1
    • 第二个’b’：在positions[1]中找> 1的位置 → 未找到

  3. “acd”：

    • ‘a’：找到位置0，prevIndex=0
    • ‘c’：在positions[2]中找> 0的位置 → 找到2，prevIndex=2
    • ‘d’：在positions[3]中找> 2的位置 → 找到3，prevIndex=3
    • 完全匹配

  4. “ace”：

    • ‘a’：找到位置0，prevIndex=0
    • ‘c’：找到位置2，prevIndex=2
    • ‘e’：在positions[4]中找> 2的位置 → 找到4，prevIndex=4
    • 完全匹配

结果：3个单词匹配

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例String[]words1={"a","bb","acd","ace"};System.out.println("Test 1: "+solution.numMatchingSubseq("abcde",words1));// 3// 测试用例2：重复单词String[]words2={"a","a","a"};System.out.println("Test 2: "+solution.numMatchingSubseq("abcde",words2));// 3// 测试用例3：空单词String[]words3={""};System.out.println("Test 3: "+solution.numMatchingSubseq("abcde",words3));// 1// 测试用例4：无匹配String[]words4={"bb","cb","bd"};System.out.println("Test 4: "+solution.numMatchingSubseq("abcde",words4));// 0// 测试用例5：完全匹配String[]words5={"abcde"};System.out.println("Test 5: "+solution.numMatchingSubseq("abcde",words5));// 1// 测试用例6：长字符串StringlongS="abcdefghijklmnopqrstuvwxyz";String[]words6={"ace","xyz","aeiou","bcdfg"};System.out.println("Test 6: "+solution.numMatchingSubseq(longS,words6));// 4// 测试用例7：单字符sString[]words7={"a","b","c"};System.out.println("Test 7: "+solution.numMatchingSubseq("a",words7));// 1// 测试用例8：大量重复单词String[]words8=newString[5000];Arrays.fill(words8,"ace");System.out.println("Test 8: "+solution.numMatchingSubseq("abcde",words8));// 5000// 测试用例9：边界情况String[]words9={"a","z"};System.out.println("Test 9: "+solution.numMatchingSubseq("a",words9));// 1// 测试用例10：空sString[]words10={"a",""};System.out.println("Test 10: "+solution.numMatchingSubseq("",words10));// 1 (只有空字符串匹配)}

关键点

  1. 缓存：

    • words数组可能包含大量重复单词
    • 缓存可以将时间复杂度从 O(total_words) 降低到 O(unique_words)

  2. 二分查找：

    • 预处理每个字符的位置，避免重复遍历s
    • 对于长s和短单词，效率提升

  3. 子序列：

    • 不需要连续，必须保持相对顺序
    • 空字符串是任何字符串的子序列

  4. 字符位置：

    • 使用 ArrayList 存储每个字符的所有位置
    • 位置天然有序，适合二分查找

  5. 边界情况处理：

    • 空字符串、单字符、重复字符等特殊情况
    • 字符在s中不存在的情况

常见问题

  1. 为什么需要缓存？

    • words可能包含重复单词
    • 不缓存会导致重复计算，效率低下

  2. 二分查找？

    • 找第一个大于prevIndex的位置
    • 确保字符的相对顺序正确
版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈，一经查实，立即删除！

河南网站建设网站建设及推广

BrainMapper终极指南：Python脑图谱分析工具从入门到精通【免费下载链接】neurosynthNeurosynth core tools项目地址: https://gitco

2026/06/30 11:56:29

孝感网站建设聊城网站建设

Dify与Postman联用进行API测试的高效开发模式在智能客服、政策问答和企业知识库日益普及的今天，AI应用早已不再是“能说会道”的玩具，而是需要稳定输出、可度量、可维

2026/06/30 13:37:06

建设网站制作江苏省建设厅网站

文章目录具体实现截图主要技术与实现手段系统设计与实现的思路系统设计方法java类核心代码部分展示结论源码lw获取/同行可拿货,招校园代理 ：文章底部获取博主联系方式！具体实

2026/06/30 13:02:34

滁州网站建设濮阳网站建设

PaddlePaddle张量并行：从原理到工业落地的深度解析在大模型时代，一个1750亿参数的语言模型已经不再令人震惊——真正让人头疼的是，如何让这样的庞然大

2026/06/30 11:53:58

杭州营销型网站建设成都市网站建设

第一章：Q#与Python变量同步概述在量子计算与经典计算混合编程的场景中，Q# 与 Python 的协同工作变得尤为重要。通过 Q# 提供的量子操作和 Python 的控

2026/06/30 11:30:25

南充网站建设富阳网站建设

人脸视频保存 -minio对象存储现在基本都是对接着网安那边.我们只需要负责身份证识别这一块 然后根据接口来判断是否成功。 详情可见认证文章身份证认证身份证+手机号码身份证+手机号码&

2026/06/30 10:18:49

网站建设软件齐齐哈尔网站建设

docker安装redis一、基本介绍二、前期准备三、docker安装redis3.1 redis镜像拉取3.2 Docker挂载redis配置文件3.3 启动redis容器3.4 验证Redis容器

2026/06/30 13:21:35

专业网站建设长沙网站建设公司

关于Dify的使用，今天介绍几种主流的使用方式与本地部署的具体教程主流使用方式方式一：使用官方提供的云服务（比较推荐）不需要折腾配置࿰

2026/06/30 13:07:34

网站建设收费行业网站建设

在现代生物制药领域，抗体药物因其高度特异性和强大的治疗潜力，成为疾病治疗的重要工具。其中，针对APRIL/CD256靶点的抗体药物，在自身免疫性

2026/06/30 11:01:53

永州网站建设遵义网站建设

网络扫描检测与psad应用全解析1. UDP扫描特性与检测UDP扫描相较于TCP扫描，由于UDP协议本身比TCP简单，且不存在类似TCP“连接”的概念，因此其扫描表现没有TCP扫描丰富。不过，ipta

2026/06/30 13:27:06