• <noscript id="e0iig"><kbd id="e0iig"></kbd></noscript>
  • <td id="e0iig"></td>
  • <option id="e0iig"></option>
  • <noscript id="e0iig"><source id="e0iig"></source></noscript>
  • leetcode438.找到字符串中所有字母異位詞

    標簽: leetcode

    1.題目描述

    給定一個字符串 s 和一個非空字符串 p,找到 s 中所有是 p 的字母異位詞的子串,返回這些子串的起始索引。

    字符串只包含小寫英文字母,并且字符串 s 和 p 的長度都不超過 20100。

    說明:

    字母異位詞指字母相同,但排列不同的字符串。
    不考慮答案輸出的順序。
    示例 1:

    輸入:
    s: "cbaebabacd" p: "abc"

    輸出:
    [0, 6]

    解釋:
    起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母異位詞。
    起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母異位詞。
     示例 2:

    輸入:
    s: "abab" p: "ab"

    輸出:
    [0, 1, 2]

    解釋:
    起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母異位詞。
    起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母異位詞。
    起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母異位詞。

    2.解題思路

    參考鏈接:https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/solution/hua-dong-chuang-kou-tong-yong-si-xiang-jie-jue-zi-/

    上述過程可以簡單地寫出如下偽碼框架:

    string s, t;
    // 在 s 中尋找 t 的「最小覆蓋子串」
    int left = 0, right = 0;
    string res = s;
    
    while(right < s.size()) {
        window.add(s[right]);
        right++;
        // 如果符合要求,移動 left 縮小窗口
        while (window 符合要求) {
            // 如果這個窗口的子串更短,則更新 res
            res = minLen(res, window);
            window.remove(s[left]);
            left++;
        }
    }
    return res;
    
    作者:labuladong
    鏈接:https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/solution/hua-dong-chuang-kou-tong-yong-si-xiang-jie-jue-zi-/
    來源:力扣(LeetCode)
    著作權歸作者所有。商業轉載請聯系作者獲得授權,非商業轉載請注明出處。

    如果上述代碼你也能夠理解,那么你離解題更近了一步。關注我的眾公號 labuladong 看更多精彩算法文章。現在就剩下一個比較棘手的問題:如何判斷 window 即子串 s[left...right] 是否符合要求,是否包含 t 的所有字符呢?

    可以用兩個哈希表當作計數器解決。用一個哈希表 needs 記錄字符串 t 中包含的字符及出現次數,用另一個哈希表 window 記錄當前「窗口」中包含的字符及出現的次數,如果 window 包含所有 needs 中的鍵,且這些鍵對應的值都大于等于 needs 中的值,那么就可以知道當前「窗口」符合要求了,可以開始移動 left 指針了。

    現在將上面的框架繼續細化:

    string s, t;
    // 在 s 中尋找 t 的「最小覆蓋子串」
    int left = 0, right = 0;
    string res = s;
    
    // 相當于兩個計數器
    unordered_map<char, int> window;
    unordered_map<char, int> needs;
    for (char c : t) needs[c]++;
    
    // 記錄 window 中已經有多少字符符合要求了
    int match = 0; 
    
    while (right < s.size()) {
        char c1 = s[right];
        if (needs.count(c1)) {
            window[c1]++; // 加入 window
            if (window[c1] == needs[c1])
                // 字符 c1 的出現次數符合要求了
                match++;
        }
        right++;
    
        // window 中的字符串已符合 needs 的要求了
        while (match == needs.size()) {
            // 更新結果 res
            res = minLen(res, window);
            char c2 = s[left];
            if (needs.count(c2)) {
                window[c2]--; // 移出 window
                if (window[c2] < needs[c2])
                    // 字符 c2 出現次數不再符合要求
                    match--;
            }
            left++;
        }
    }
    return res;
    
    作者:labuladong
    鏈接:https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/solution/hua-dong-chuang-kou-tong-yong-si-xiang-jie-jue-zi-/
    來源:力扣(LeetCode)
    著作權歸作者所有。商業轉載請聯系作者獲得授權,非商業轉載請注明出處。

    上述代碼已經具備完整的邏輯了,只有一處偽碼,即更新 res 的地方,不過這個問題太好解決了,直接看解法吧!

    string minWindow(string s, string t) {
        // 記錄最短子串的開始位置和長度
        int start = 0, minLen = INT_MAX;
        int left = 0, right = 0;
        
        unordered_map<char, int> window;
        unordered_map<char, int> needs;
        for (char c : t) needs[c]++;
        
        int match = 0;
        
        while (right < s.size()) {
            char c1 = s[right];
            if (needs.count(c1)) {
                window[c1]++;
                if (window[c1] == needs[c1]) 
                    match++;
            }
            right++;
            
            while (match == needs.size()) {
                if (right - left < minLen) {
                    // 更新最小子串的位置和長度
                    start = left;
                    minLen = right - left;
                }
                char c2 = s[left];
                if (needs.count(c2)) {
                    window[c2]--;
                    if (window[c2] < needs[c2])
                        match--;
                }
                left++;
            }
        }
        return minLen == INT_MAX ?
                    "" : s.substr(start, minLen);
    }
    
    作者:labuladong
    鏈接:https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/solution/hua-dong-chuang-kou-tong-yong-si-xiang-jie-jue-zi-/
    來源:力扣(LeetCode)
    著作權歸作者所有。商業轉載請聯系作者獲得授權,非商業轉載請注明出處。

     

    vector<int> findAnagrams(string s, string t) {
        // 用數組記錄答案
        vector<int> res;
        int left = 0, right = 0;
        unordered_map<char, int> needs;
        unordered_map<char, int> window;
        for (char c : t) needs[c]++;
        int match = 0;
        
        while (right < s.size()) {
            char c1 = s[right];
            if (needs.count(c1)) {
                window[c1]++;
                if (window[c1] == needs[c1])
                    match++;
            }
            right++;
    
            while (match == needs.size()) {
                // 如果 window 的大小合適
                // 就把起始索引 left 加入結果
                if (right - left == t.size()) {
                    res.push_back(left);
                }
                char c2 = s[left];
                if (needs.count(c2)) {
                    window[c2]--;
                    if (window[c2] < needs[c2])
                        match--;
                }
                left++;
            }
        }
        return res;
    }
    
    作者:labuladong
    鏈接:https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/solution/hua-dong-chuang-kou-tong-yong-si-xiang-jie-jue-zi-/
    來源:力扣(LeetCode)
    著作權歸作者所有。商業轉載請聯系作者獲得授權,非商業轉載請注明出處。

    3.代碼實現

    方法一:思路與leetcode76.最小覆蓋子串 一樣

    class Solution(object):
        def findAnagrams(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: List[int]
            """
            from collections import Counter
            if not s or not p:
                return []
            size=len(p)
            HashMap = Counter(p)
            left=0
            cnt=0
            res=[]
            for i in range (len(s)):
                HashMap[s[i]]=HashMap[s[i]]-1
                if HashMap[s[i]]>=0:
                    cnt+=1
                while cnt==size:
                    if i-left+1==size :
                        res.append(left)
                    HashMap[s[left]]=HashMap[s[left]] + 1
                    if HashMap[s[left]] > 0:
                        cnt-=1
                    left+=1
            return res

    方法二:上一章思路實現

    class Solution(object):
        def findAnagrams(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: List[int]
            """
            
            from collections import Counter
            if not s or not p:
                return []
            needs = Counter(p)
            window = {}
            match = 0
            left = 0
            right = 0
            res = []
            while right < len(s):
                if s[right] in needs:
                    window[s[right]] = window.get(s[right],0)+1
                    if window[s[right]] == needs[s[right]]:
                        match += 1
                right += 1
                while match == len(needs):
                    # 這個時候right在前面+過1,指向的窗口外的第一個
                    if right - left == len(p):
                        res.append(left)
                    if s[left] in needs:
                        window[s[left]] -= 1
                        if window[s[left]] < needs[s[left]]:
                            match -= 1
                    left += 1
            return res
    
    

     

    版權聲明:本文為qq_28468707原創文章,遵循 CC 4.0 BY-SA 版權協議,轉載請附上原文出處鏈接和本聲明。
    本文鏈接:https://blog.csdn.net/qq_28468707/article/details/103566801

    智能推薦

    (C++)二叉樹的線索化 / 線索二叉樹

    好久不見,朋友們!雖然我知道沒人看我的博客,但我還是想叨逼叨一下。啊,好久沒編程了(其實也就一周沒編),但你們知道,程序員一天不編程那能叫程序員么???雖然我不是程序員哈哈哈哈哈,但還是要有基本素養嘛。 繼續寫二叉樹,給自己立一個flag,就是這幾天要寫完之前沒做完的幾道題,和二叉樹紅黑樹各種樹之類的~~雖然有這個flag,但我還是很實誠地遵從自己的內心,買了一張明天的電影票,等我回來告訴你們好不...

    Linux內存管理:分頁機制

    《Linux內存管理:內存描述之內存節點node》 《Linux內存管理:內存描述之內存區域zone》 《Linux內存管理:內存描述之內存頁面page》 《Linux內存管理:內存描述之高端內存》 《Linux內存管理:分頁機制》 《內存管理:Linux Memory Management:MMU、段、分頁、PAE、Cache、TLB》 目錄 1 分頁機制 1.1 為什么使用多級頁表來完成映射 ...

    Logtail 混合模式:使用插件處理文件日志

    作為一個服務百萬機器的日志采集 agent,Logtail 目前已經提供了包括日志切分、日志解析(完整正則、JSON、分隔符)、日志過濾在內的常見處理功能,能夠應對絕大多數場景的處理需求。但有些時候,由于應用的歷史原因或是本身業務日志的復雜性,單一功能可能無法滿足所采集日志的處理需求,比如: 日志可能不再是單一格式,有可能同時由 JSON 或者分隔符日志組成。 日志格式可能也不固定,不同的業務邏輯...

    Q版緩沖區溢出教程-第一章讀書筆記

    Q版緩沖區溢出教程 1.3 神秘的windows系統 1.3.1 溢出舉例: 我們編譯運行之后的結果 現在我們把程序進行更改,數組的值進行一個變化,改為’abcdefgh’然后再編譯運行 程序運行沒有問題。 如果這個時候我們把程序再次加長的話,會發生什么,內容更改為’abcdefghijklmn’。 這個時候出了錯誤說內存越界。 1.3.3對溢出報錯...

    CVPR2014 Objectness BING 源碼編譯

    CVPR2014 Objectness BING 源碼編譯 轉載請注明作者和出處:http://blog.csdn.net/u011475210 操作系統:WINDOWS 10 軟件版本:VS2013+OpenCV2.4.13 編者: WordZzzz CVPR2014 Objectness BING 源碼編譯 一資源 二環境配置 一、資源 1.論文作者主頁:http://mmcheng.net/...

    猜你喜歡

    HelloSpringMVC

    配置版:理解原理使用 新建Moudle,添加web支持 確定導入了SpringMVC依賴 配置web.xml,注冊DispatcherServlet 編寫SpringMVC的配置文件spring-mvc-servlet.xml 注意:官方名稱要求:[servletname]-servlet 在servlet.xml中添加處理映射器 在servlet.xml中添加處理器適配器 在servlet.xm...

    小程序設置單個頁面頭部title字體色及背景色

    小程序設置單個頁面頭部title字體色及背景色 項目里的一個頁面白底黑字顯得很突兀,想更改一下頭部配色,上圖: 查找了文檔,發現可以修改,見鏈接: https://developers.weixin.qq.com/miniprogram/dev/api/ui/navigation-bar/wx.setNavigationBarColor.html 直接在onLoad中寫就ok,(基礎庫1.4.0才...

    (2)Spring IoC的第一個例子

    使用Eclipse,開濤老師安裝了一個插件,SpringSource Tool Suite,不知道實際是干什么的,先不安裝了。 開發環境:jdk1.8,Eclipse Oxygen(新版的eclipse),spring-framework-4.3.10.RELEASE 核心包,比開濤老師的少了一個asm,貌似又跟core合并了。 還需要幾個其它的包 創建一個java project項目 新建一個文...

    力扣:把數組排成最小的數,以字符串形式輸出(排序)

    先上源代碼: 整體思路: 將數組按照最小數的形式排好序 把數組的每個元素賦給字符串 返回一個字符串 我們需要注意幾個點: 運用qsort()函數排序,需要自己寫一個排序函數。 sprintf()函數的使用, sprintf(目標字符串,“原元素的格式”,原元素); 例如:int a[40],char s[40]; sprintf(s,"%d",a[1])...

    pytorch 卷積神經網絡識別Fashion-MNIST

    一、導包 二、訓練集圖像數據準備 三、獲取一個batch的圖像,將其可視化 四、測試數據集處理 五、卷積神經網絡的搭建 六、卷積神經網絡預測與訓練—定義網絡的訓練過程函數 七、對指定的模型和優化器進行訓練 八、可視化損失函數訓練過程 九、測試集預測,并使用混淆矩陣熱力圖可視化...

    精品国产乱码久久久久久蜜桃不卡