专栏首页Petrichor的专栏leetcode: 30. Substring with Concatenation of All Words [✗]

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

Problem

# 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

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]

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • numpy: np.asarray 函数

    简而言之: 主要区别在于 np.array (默认情况下)将会copy该对象,而 np.asarray 除非必要,否则不会copy该对象。

    JNingWei
  • python: cmp 内建函数 (py3中被取缔)

    比较两个对象x和y:如果x < y ,返回负数;x == y,返回0;x > y,返回正数。

    JNingWei
  • aptitude指令

    aptitude update #更新可用的包列表 aptitude upgrade #升级可用的包 aptitude dist-upgrad...

    JNingWei
  • 堪比顶流的“丁真”,名字被抢注商标了!

    刚过去的11月,藏族小伙丁真顺利出圈。在一支不到10秒的抖音视频中,他身着藏袍,一张野性又纯真的脸庞吸引了众多迷妹。一时间关于他的热搜,一条接着一条,人气不亚...

    腾讯云DNSPod团队
  • GitHub秒变GayHub

    江湖一直有传闻:三流程序员写UI,二流程序员写框架,一流程序员写算法,顶级程序员穿女装。

    xcbeyond
  • 效率脚本:删除已经合并的git分支

    使用Git管理代码工程,着实方便了很多,但是当做完feature分支或者完成hotfix之后,总是忘记删除这些无用的分支,一个一个地删除着实麻烦,重复手工劳动不...

    技术小黑屋
  • H7-TOOL多功能开发工具/开源/烧录器/示波器/仿真器/逻辑分析仪

    H7-TOOL的最终目标: 1、为单片机工程师提供一款实用的多功能开发调试工具。 2、相信很多人有带板子回家调试、或带板子出差调试的情况。因为产品问题是无法...

    armfly
  • 淘宝的npaliedit在mb下会崩溃的问题解决了

    龙泉寺扫地僧
  • 腾讯经济体轰鸣:AI引擎、数字化助手,一切上云

    腾讯总裁解释,数字化进程浩浩汤汤,腾讯去年为此专门架构调整,新成立两大事业群:一个是To C的内容与平台事业群。另一个是To B的云与智慧产业事业群(CSIG)...

    量子位
  • 调用CodeSmith类库实现代码生成(含源码)

          CodeSmith的作用是不言而喻的,用过的人都会觉得它非常强大.根据自定义模板,快速生成代码.只是我们使用的时候,要在它提供的CodeSmith ...

    用户1219352

扫码关注云+社区

领取腾讯云代金券