Leetcode 30 Substring with Concatenation of All Words 无序map的应用细节

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given: s: "barfoothefoobarman" words: ["foo", "bar"]

You should return the indices: [0,9].

(order does not matter).

这题意外的收获还是挺大的!恶魔总在细碎处。

题意就是在给定串S中,找出包含且只包含给定字典中所有词的子串的起始位置,并且任意两个词中间不能有交叉字母。

先说说unordered_map。在做这题之前我是不知道这个数据结构的,我只会用map,这题学到了。

两者的接口等基本一致,写代码会map的话,应该也会unordered_map。

map的实现是红黑树,因而修改,查询等操作复杂度是log级别的,同时它的元素也是有序的;

而unordered_map的实现是散列表,基本操作的复杂度是常数级别的,同时元素是无序的;

显然在不关心元素顺序的情况下,后者是通常是更好的选择。

值得一提的是,关于map的find函数,我在实际做题的时候有了新的认识,这点在代码中再说。

再说说思路。

两层循环,第一层列举起始位置0~len-1,第二层以len为步长向后便利,对于遍历到的词分三种情况:

1.在map中,且总共出现的次数未达到字典中的次数;

把这个词加入字符串,继续向后扫描,判断词数是否等于字典大小,等于则求得其中一个结果。

2.在map中,但总共出现的次数已经达到字典中的次数;

从头开始,去掉这个词第一次出现位置之前的所有词,把这个词加入字符串,继续向后扫描。

3.未在map中。

去掉前面所有的词,直接从下一个词开始。

关于时间复杂度,有很多人觉得是word[0].length()*S.length(),其实不然,

第一层循环的复杂度确实为word[0].length(),然而由于第二层的步长为word[0].length(),

所以实际的复杂度依然为S.length(),也就是说是线性的。

<span style="color:#333333;">class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> mp;
        vector<int> result;
        unordered_map<string, int>::iterator it;
        int len=words[0].length(),num=words.size();
        for(int i=0;i<len;i++) //起点
        {
            for(int i=0;i<num;i++)
                mp[words[i]]++;
            int st=i,cnt=0;
            for(int j=i;j<s.length();j+=len) 
            {
                string now=s.substr(j,len);
                if(mp.find(now)!=mp.end()) //这里两个判断语句的逻辑顺序进行了调整,不相信可以试试先mp[now]>0,后find(now)时的结果
                {
                    if(mp[now]>0) //这里访问了mp[now],所以即使now不存在,在经过这次访问后程序也自动为它分配了空间
                    {                //如果find在这之后调用,虽然逻辑上now不存在,但是内存中已然存在,得到的find结果会和想象中不同
                        mp[now]--;
                        if(++cnt==num)
                        {
                            result.push_back(st);
                            mp[s.substr(st,len)]++;
                            st+=len;
                            cnt--;
                        }
                    }
                    else
                    {
                        for(int k=st;k<j;k+=len)
                        {
                            if(s.substr(k,len)==now)
                            {
                              st=k+len;
                              break;
                            }
                            else
                            {
                                mp[s.substr(k,len)]++;
                                cnt--;
                            }
                        }
                    }
                }
                else
                {
                    for(int k=st;k<j;k+=len)
                        mp[s.substr(k,len)]++;
                    st=j+len;
                    cnt=0;
                }
            }
            mp.clear();
        }
        return result;
    }
};</span>

先说说unordered_map。在做这题之前我是不知道这个数据结构的,我只会用map,这题学到了。

两者的接口等基本一致,写代码会map的话,应该也会unordered_map。

map的实现是红黑树,因而修改,查询等操作复杂度是log级别的,同时它的元素也是有序的;

而unordered_map的实现是散列表,基本操作的复杂度是常数级别的,同时元素是无序的;

显然在不关心元素顺序的情况下,后者是通常是更好的选择。

值得一提的是,关于map的find函数,我在实际做题的时候有了新的认识,这点在代码中再说。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法channel

机器学习|海量数据求top K 之最小堆实现

01 — 要求 从海量数据中按照某个规则找出前K名,简化起见,从一个海量的整形数组中,找出前K个最大元素。 无法直接一次性读入内存,可以将文件依次分批读入,找出...

44560
来自专栏编舟记

泛型编程

泛型编程是一种编程风格,其中算法以尽可能抽象的方式编写,而不依赖于将在其上执行这些算法的数据形式。

9720
来自专栏ml

向前字典排序

          next_permutation算法对区间元素进行一次组合排序,使之字典顺序大于原来的排序,有如下两个使用原形,对迭代器区间[first,l...

27990
来自专栏程序员叨叨叨

5.3 结构类型

Cg 语言支持结构体(structure),实际上 Cg 中的结构体的声明、使用和 C++ 非常类似(只是类似,不是相同)。一个结构体相当于一种数据类型,可以定...

6220
来自专栏mySoul

设计模式-UML关系基础

12450
来自专栏灯塔大数据

技术 | Python从零开始系列连载(二十四)

为了解答大家学习Python时遇到各种常见问题,小灯塔特地整理了一系列从零开始的入门到熟练的系列连载,每周五准时推出,欢迎大家学积极学习转载~

11120
来自专栏偏前端工程师的驿站

基础野:细说浮点数

Brief                                 本来只打算理解JS中0.1 + 0.2 == 0.30000000000000004...

22390
来自专栏xcywt

《大话数据结构》一些基础知识

第一章 数据结构绪论 1.4 基本概念和术语 1.4.1 数据 数据:描述客观事物的符号,是计算机中可以操作的对象,是能被极端及识别,并输入给计算机处理的符号集...

35790
来自专栏java一日一条

最快最简单的排序算法:桶排序

在我们生活的这个世界中到处都是被排序过的。站队的时候会按照身高排序,考试的名次需要按照分数排序,网上购物的时候会按照价格排序,电子邮箱中的邮件按照时间排序……总...

11510
来自专栏JavaEdge

设计模式实战 - 解释器模式(Interpreter Pattern)

● 公式可以运行时编辑,并且符合正常算术书写方式,例如a+b-c ● 高扩展性,未来增加指数、开方、极限、求导等运算符号时较少改动 ● 效率可以不用考虑,晚...

12520

扫码关注云+社区

领取腾讯云代金券