題目

給你一個(gè)字符串?dāng)?shù)組 patterns 和一個(gè)字符串 word ，統(tǒng)計(jì) patterns 中有多少個(gè)字符串是 word 的子字符串。返回字符串?dāng)?shù)目。
子字符串 是字符串中的一個(gè)連續(xù)字符序列。
示例 1：
輸入：patterns = [“a”,“abc”,“bc”,“d”], word = “abc”
輸出：3
解釋：

• “a” 是 “abc” 的子字符串。
• “abc” 是 “abc” 的子字符串。
• “bc” 是 “abc” 的子字符串。
• “d” 不是 “abc” 的子字符串。
  patterns 中有 3 個(gè)字符串作為子字符串出現(xiàn)在 word 中。
  示例 2：
  輸入：patterns = [“a”,“b”,“c”], word = “aaaaabbbbb”
  輸出：2
  解釋：
• “a” 是 “aaaaabbbbb” 的子字符串。
• “b” 是 “aaaaabbbbb” 的子字符串。
• “c” 不是 “aaaaabbbbb” 的字符串。
  patterns 中有 2 個(gè)字符串作為子字符串出現(xiàn)在 word 中。
  示例 3：
  輸入：patterns = [“a”,“a”,“a”], word = “ab”
  輸出：3
  解釋：patterns 中的每個(gè)字符串都作為子字符串出現(xiàn)在 word “ab” 中。
  提示：
  1 <= patterns.length <= 100
  1 <= patterns[i].length <= 100
  1 <= word.length <= 100
  patterns[i] 和 word 由小寫英文字母組成
  來(lái)源：力扣（LeetCode）

解題思路

??檢查pattern里的元素是否是word的字串，可以使用暴力匹配，也可以使用kmp。

class Solution:def numOfStrings(self, patterns: List[str], word: str) -> int:count=0for i in patterns:if re.search(i,word):count+=1return count

??KMP:

class Solution:def numOfStrings(self, patterns: List[str], word: str) -> int:def KMP(haystack: str, needle: str) -> int:n=len(needle)m=len(haystack)needle=' '+needle  #添加哨兵haystack=' '+haystackNext=[0]*(n+1)i,j=1,0while i<n:  #求next數(shù)組if j==0 or needle[i]==needle[j]:i+=1j+=1if needle[i]!=needle[j]:Next[i]=jelse:Next[i]=Next[j]else:j=Next[j]i,j=1,1while i<=m and j<=n: #KMPif j==0 or haystack[i]==needle[j]:i+=1j+=1else:j=Next[j]return i-n-1 if j>n else -1count=0for i in patterns:if KMP(word,i)!=-1:count+=1return count

總結(jié)

以上是生活随笔為你收集整理的LeetCode简单题之作为子字符串出现在单词中的字符串数目的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。