題目

難度：★★★☆☆

類型：字符串

方法：滑動窗口

力扣鏈接請移步本題傳送門

更多力扣中等題的解決方案請移步力扣中等題目錄

給定兩個字符串 s1 和 s2，寫一個函數來判斷 s2 是否包含 s1 的排列。

換句話說，第一個字符串的排列之一是第二個字符串的子串。

示例1:

輸入: s1 = "ab" s2 = "eidbaooo"

輸出: True

解釋: s2 包含 s1 的排列之一 ("ba").

示例2:

輸入: s1= "ab" s2 = "eidboaoo"

輸出: False

注意：

輸入的字符串只包含小寫字母

兩個字符串的長度都在 [1, 10,000] 之間

解答

首先我們回顧一下排列的定義。從一個數量為n的集合中抽取出來m個樣本，按照任意順序擺放起來，就可以稱為原始集合的一個排列，如果m=n，那么這種排列就是原始集合的一個全排列。全排列有一個特性，即全排列中任意一種情況的樣本，都可以在原始集合中找到，除了順序之外略有差別，每個樣本的出現次數與原始集合完全一致。

對于這道題目，為了找到長串s2中是否包含子串s1的全排列，只需要指定一個長度與段串s1一致的窗口，滑動窗口并統計窗口中各個元素出現次數是否與短串s1完全一致，如果一致，表明窗口中的子串與s1互為全排列。根據此可解決該問題。

class Solution:

def checkInclusion(self, s1: str, s2: str) -> bool:

if len(s1) > len(s2):

return False

c1 = {chr(i): 0 for i in range(97, 97+26)}

cur = c1.copy()

for a in s1:

c1[a] += 1

for i in range(len(s2)):

cur[s2[i]] += 1

if i >= len(s1):

cur[s2[i - len(s1)]] -= 1

if c1 == cur:

return True

return False

如有疑問或建議，歡迎評論區留言~

有關更多力扣中等題的python解決方案，請移步力扣中等題解析

總結

以上是生活随笔為你收集整理的python输入字符串从大到小排列_567. 字符串的排列（Python）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。