专栏首页Michael阿明学习之路LeetCode 30. 串联所有单词的子串(字符串哈希)

LeetCode 30. 串联所有单词的子串(字符串哈希)

1. 题目

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配,中间不能有其他字符,但不需要考虑 words 中单词串联的顺序。

示例 1:
输入:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
输出:[0,9]
解释:
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2:
输入:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
输出:[]

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

  • 将字符串转换成128进制的数字
typedef unsigned long long ull;
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        if(words.empty() || words.size()*words[0].size() > s.size()) 
        	return {};
        int i, j, wlen = words[0].size(), n = words.size();
        unordered_map<ull,int> m;
        for(auto& w : words)
        {
        	ull v = 0;
        	for(char ch : w)
        		v = v*128+ch;
        	m[v]++;//字符转成128进制的数,计数
        }
        //字符串s每个位置开始后的wlen个字符的ull表示
        vector<ull> hashv(s.size(),0);
        ull pown = 1;
        for(i = 0; i < wlen; ++i)
        {
        	pown *= 128;
        	hashv[0] = hashv[0]*128+s[i];
        }
        for(i = 1; i <= s.size()-wlen; ++i)
        {
        	hashv[i] = hashv[i-1]*128-s[i-1]*pown+s[i+wlen-1];
        }

        vector<int> ans;
        bool ok;
        for(i = 0; i <= s.size()-n*wlen; ++i)
        {
        	unordered_map<ull, int> temp(m);
        	ok = true;
        	for(j = i; j < n*wlen+i; j+=wlen)
        	{
        		if(--temp[hashv[j]] < 0)
        		{
        			ok = false;
        			break;
        		}
        	}
        	if(ok) ans.push_back(i);
        }
        return ans;
    }
};

584 ms 126.6 MB

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 1408. 数组中的字符串匹配(暴力查找)

    给你一个字符串数组 words ,数组中的每个字符串都可以看作是一个单词。请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词。

    Michael阿明
  • LeetCode 953. 验证外星语词典

    某种外星语也使用英文小写字母,但可能顺序 order 不同。 字母表的顺序(order)是一些小写字母的排列。

    Michael阿明
  • LeetCode 318. 最大单词长度乘积(位运算)

    给定一个字符串数组 words,找到 length(word[i]) * length(word[j]) 的最大值,并且这两个单词不含有公共字母。你可以认为每个...

    Michael阿明
  • 基于游标的分页接口实现

    分页接口的实现,在偏业务的服务端开发中应该很常见,PC时代的各种表格,移动时代的各种feed流、timeline。

    贾顺名
  • 论 STA | STA之AOCV

    今儿接着《绿蚁新醅酒,红泥小火炉:STA之OCV》来聊AOCV,AOCV全称:Advanced OCV,T家叫SBOCV,总是忍不住联想到傻逼OCV,实际上是:...

    老秃胖驴
  • Spark Scala当中reduceByKey的用法

    /*reduceByKey(function) reduceByKey就是对元素为KV对的RDD中Key相同的元素的Value进行function的reduce...

    马克java社区
  • 第193天:js---Math+Error+Number+Object总结

    半指温柔乐
  • 优化算法——OWL-QN

        在机器学习中,正则化是相对于过拟合出现的一种特征选择的方法。在机器学习算法中使用的Loss项为最小化误差,而最小化误差是为了让我们的模型拟合我们的训练数...

    zhaozhiyong
  • Spring+SpringMVC+MyBatis+easyUI整合基础篇(八)mysql中文查询bug修复

    前言   在测试搜索时出现的问题,mysql通过中文查询条件搜索不出数据,但是英文和数字可以搜索到记录,中文无返回记录。本文就是写一下发现问题的过程及解决方法...

    我是十三
  • Echarts动态加载后台数据

    后台Controller:根据业务需求不同而返回不同数据,我前台要循环遍历Echarts的series进行数据添加,所以后台返了个二维数组过去。

    wfaceboss

扫码关注云+社区

领取腾讯云代金券