leetcode-792匹配子序列的单词数(桶)

leetcode-792匹配子序列的单词数(桶)原题链接给定字符串 S 和单词字典 words, 求 words[i] 中是 S 的子序列的单词个数。示例:输入: S = “abcde”words = [“a”, “bb”, “acd”, “ace”]输出: 3解释: 有三个是 S 的子序列的单词: “a”, “acd”, “ace”。注意:所有在words和 S 里的单词都只由小写字母组成。S 的长度在 [1, 50000]。words 的长度在 [1, 5000]。words[i]的长度在[1, 50]。题解暴力

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

原题链接

给定字符串 S 和单词字典 words, 求 words[i] 中是 S 的子序列的单词个数。

示例:

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

注意:

  • 所有在words和 S 里的单词都只由小写字母组成。
  • S 的长度在 [1, 50000]。
  • words 的长度在 [1, 5000]。
  • words[i]的长度在[1, 50]。

题解

  1. 暴力
class Solution { 
   
public:
    int numMatchingSubseq(string s, vector<string>& words) { 
   
        int res = 0;
        for(auto &word : words){ 
   
            int j = 0,len = 0;
            for(int i = 0;i < s.size();i ++){ 
   
                if(word[j] == s[i])len ++,j ++;
            }
            if(len == word.size())res ++;
        }
        return res;
    }
};
  1. 借鉴桶排序,把所有单词的字符按照word[0]放入对应桶,当字符串扫到对应字符的时候就把桶中的单词放入下一个字符对应的桶即可
class Solution { 
   
public:
    int numMatchingSubseq(string s, vector<string>& words) { 
   
        vector<pair<string,int> > v[26];
        int res = 0;
        for(auto &w : words){ 
   
            v[w[0] - 'a'].push_back({ 
   w,0});
        }
        for(int i = 0;i < s.size();i ++){ 
   
            int c = s[i] - 'a';
            vector<pair<string,int> > t = v[c];
            v[c].clear();
            for(auto &a : t){ 
   
                if(a.second == a.first.size() - 1)res ++;
                else v[a.first[a.second + 1] - 'a'].push_back({ 
   a.first,a.second + 1});
            }
        }
        return res;
    }
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168735.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 捕获RuntimeException

    捕获RuntimeException捕获RuntimeExceptionruntimeException在java中是不被检查的,如何让抛出的runtimeException能够捕获到,并进行相应的处理。try{ //调用可能出现runtimeException的方法 XXXXXXXXXXXXXXXX}catch(Exceptione){ try{ throwe.getCause(); }catch(Throwableth){ //进行相应的捕获之后的处理 XXXXXXXXXXXXXXXXXX }}.

  • 左右presentViewController经background黑问题

    左右presentViewController经background黑问题

  • 【数字图像处理】C++读取、旋转和保存bmp图像文件编程实现

    【数字图像处理】C++读取、旋转和保存bmp图像文件编程实现通过我这些天用C++读写bmp图像的经历,摸索再摸索,终于对bmp文件的结构、操作有了一定的了解,下面就大概介绍bmp图片纯C++的读取、旋转和保存的实现过程。要用C++读取bmp图片文件,首先要弄清楚bmp格式图片文件的结构。可以参考这篇文章:http://blog.csdn.net/xiajun07061225/article/details/5813726有几点需要注意的是:在读

  • 正规矩阵(酉矩阵)[通俗易懂]

    正规矩阵(酉矩阵)[通俗易懂]英文名:Unitarymatrix

  • 4.2.1越狱

    4.2.1越狱
    这是我见过的最简单的越狱方法了!操作成功,绝对简单可用·
     
     
    越狱并非高不可攀,也并非可怕至极,只要不慌张、耐心,一步步来,就没有问题。
    一、升级到4.2.1系统。
          先在威锋网里下载ipad4.2.1固件http://bbs.weiphone.com/read-htm-tid-862081.html,记住下载后的存放位置,然后把ipad连接到电脑,打开itunes,按住shift键点更新,选择刚下载的固件,把系统升级到4.

  • 高性能php7_php5升级到php7

    高性能php7_php5升级到php7研究PHP7技术的背景公司开源节流的大背景下我们需要节省成本PHP7相对于现在魅族线上的版本5.5性能提升至少一倍以上社区日活用户增长迅速(15年数据日均PV年增长348%日均UV年增长112%)移动互联网的大环境下要求我们的程序能够更快的速度响应用户的请求以满足更好的用户体验对新技术的求知欲望(满足自己的一点点虚荣心)PHP7性能小记PHP7性能初印象(比PHP5.4提升

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号