LeetCode 30. 串联所有单词的子串

作者:神秘网友 发布时间:2021-02-26 15:20:12

LeetCode 30. 串联所有单词的子串

题目:


给定一个字符串 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"]
输出:[]

思路:

脑子不灵光,可以想出滑动的指针方法, 但是写不出来...

暴力搜索是我最后的倔强~~~~

方法一:

暴力搜索~~~

以words中一个str的长度(题目条件是每个元素长度都相同),进行查找。因为不用考虑顺序,所以只要从s中截取的部分包含在words(因为是匹配该列表,每次都循环都需要该对象,所以用切片copy)中就可以remove掉,没有就不符合条件跳出,当列表长度为0的时候,index即符合条件。

class Solution(object):
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        if len(words)==0 or len(s)==0:
            return []

        wl=len(words[0])
        ss=[]
        for i in range(len(s)-wl*len(words)+1):
            tw=words[:] #需要用切片深copy匹配串
            k=i
            while len(tw)!=0:
                if s[k:k+wl] in tw: #当等间距长度检索的字符包含在匹配串中 ,就remove
                    tw.remove(s[k:k+wl])
                    k+=wl
                else:
                    break
            if len(tw)==0: #长度为0即为符合条件的index,塞入数组
                ss.append(i)
        
        return ss

方法二:

摘自题解summer_tree ,思路很清晰~我也有想到双指针移动,但是写不出~~苦恼

LeetCode 30. 串联所有单词的子串 相关文章

  1. 疑问Leetcode/数组/两数之和

    题目 给定一个整数数组 nums和一个整数目标值 target,请你在该数组中找出 和为目标值 的那两个整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 你可以按任意顺序返回答案。 示例 1: 输入:nums =

  2. 【栈和队列】leetcode20——有效的括号

    编号20:有效的括号 给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。 示例 1:输入: "()"输出: true

  3. 力扣 哈希算法

    目录 Leetcode #1178 猜字谜 方法:状态压缩 + 子集 + 哈希位运算 Leetcode #1178 猜字谜 题名:猜字谜 描述: 外国友人仿照中国字谜设计了一个英文版猜字谜小游戏,请你来猜猜看吧。 字谜的迷面puzzle 按字符串形式给出,如果一个单词word符合下面两个条件,

  4. [LeetCode 42.] 接雨水

    LeetCode 42. 接雨水 题目描述 给定n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,

  5. [LeetCode] 1041. Robot Bounded In Circle 困于圆圈路径中的机器人

    On an infinite plane, a robot initially stands at (0, 0) and faces north. The robot can receive one of three instructions: "G" : go straight 1 unit; "L" : turn 90 degrees to the left; "R" : turn 90 degrees to the right. The robot performs

  6. django学习-30.发送邮件正文值为字符串的单个/多个邮件

    1.写这篇博客的目的 主要记录如何通过django来实现这个功能:发送邮件正文值为字符串的单个/多个邮件; django的发邮件的功能很简单发邮件的相关代码已经封装好了: 发送邮件正文值为字符串的单个邮件,使用该函数:send_mail(); 发送邮件正文值为字符串的

  7. LeetCode——38. 外观数列

    题目介绍 题干:给定一个正整数 n ,输出外观数列的第 n 项。「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。你可以将其视作是由递归公式定义的数字字符串序列:countAndSay(1) = "1"countAndSay(n) 是对 countAndSay(n-1)

  8. 删除链表的倒数第N个结点(leetcode19)

    给你一个链表,删除链表的倒数第n个结点,并且返回链表的头结点。 进阶:你能尝试使用一趟扫描实现吗 示例 1: 输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5] 解析: 对链表操作时,一种常用的技巧:添加一个哑节点,使它的next指向链表的头结点。 这样

  9. LeetCode | 0623. 在二叉树中增加一行【Python】

    问题 力扣 给定一个二叉树,根节点为第1层,深度为 1。在其第 d 层追加一行值为 v 的节点。 添加规则:给定一个深度值 d (正整数),针对深度为 d-1 层的每一非空节点 N,为 N 创建两个值为 v 的左子树和右子树。 将 N 原先的左子树,连接为新节点 v 的左子

  10. leetcode刷题笔记-700. 二叉搜索树中的搜索(java实现)

    题目描述 给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。 例如, 给定二叉搜索树: 4 / \ 2 7 / \ 1 3 和值: 2 你应该返回如下子树: 2 / \ 1 3 在上述示例中,

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2020, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词