前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 30. 串联所有单词的子串(字符串哈希)

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

作者头像
Michael阿明
发布2020-07-13 15:10:07
7280
发布2020-07-13 15:10:07
举报
文章被收录于专栏:Michael阿明学习之路

1. 题目

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

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

代码语言:javascript
复制
示例 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进制的数字
代码语言:javascript
复制
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

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/05/30 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 题目
  • 2. 解题
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档