KMP内容没看:明天面试完再看!!!
https://programmercarl.com/0028.实现strStr.html#思路
28.找出字符串中第一个匹配项的下标
28. 找出字符串中第一个匹配项的下标 - 力扣(LeetCode)
给你两个字符串 haystack
和 needle
,请你在 haystack
字符串中找出 needle
字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle
不是 haystack
的一部分,则返回 -1
。
- 示例 1:
- 输入:haystack = "sadbutsad", needle = "sad"
- 输出:0
- 解释:"sad" 在下标 0 和 6 处匹配。第一个匹配项的下标是 0 ,所以返回 0 。
- 示例 2:
- 输入:haystack = "leetcode", needle = "leeto"
- 输出:-1
- 解释:"leeto" 没有在 "leetcode" 中出现,所以返回 -1 。
解题思路:
库函数find:先判断n是否在h中,若在h.find(s)
class Solution():
def strStr(haystack,needle):
if needle not in haystack:
return -1
return haystack.find(needle)
459.重复的字符串
459. 重复的子字符串 - 力扣(LeetCode)
给定一个非空的字符串 s
,检查是否可以通过由它的一个子串重复多次构成。
- 示例 1:
- 输入: s = "abab"
- 输出: true
- 解释: 可由子串 "ab" 重复两次构成。
- 示例 2:
- 输入: s = "aba"
- 输出: false
- 示例 3:
- 输入: s = "abcabcabcabc"
- 输出: true
- 解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
解题思路:
假设法:设s是由n个x组成,那么s+s是由2n个x组成,对s+s去除收尾元素,则 (s+s)[1:-1]是由2n-2个x组成,若s存在于(s+s)[1:-1]中,可以得出(2n-2)x>=nx,进一步得到n>=2,证明s是由大于2个n组成
class Solution():
def repeatedSubstringPattern(s):
return s in (s+s)[1:-1]