前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode: 30. Substring with Concatenation of All Words [✗]

leetcode: 30. Substring with Concatenation of All Words [✗]

作者头像
JNingWei
发布2018-09-28 11:30:41
3610
发布2018-09-28 11:30:41
举报
文章被收录于专栏:JNing的专栏

Problem

代码语言:javascript
复制
# 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).

AC

代码语言:javascript
复制
class Solution():
    def findSubstring(self, s, words):
        import collections
        dict  = collections.defaultdict(int)
        for w in words:
            dict[w] += 1
        res, l = [], len(words[0])
        for i in range(l):
            dict1, j = dict.copy(), i
            while j < len(s) - l + 1:
                dict1[s[j:j+l]] -= 1
                while dict1[s[j:j+l]] < 0:
                    dict1[s[i:i+l]] += 1
                    i += l
                j += l
                if (j-i) / l == len(words) :
                    res.append(i)
        return res


if __name__ == "__main__":
    assert Solution().findSubstring("barfoothefoobarman", ["foo", "bar"]) == [0, 9]
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017年11月08日,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

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

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