亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

[Leetcode] Substring with Concatenation of All Wor

adie / 415人閱讀

摘要：每次搜索中，我們通過(guò)哈希表維護(hù)一個(gè)窗口，比如中，我們先拿出。如果都不在數(shù)組中，那說(shuō)明根本不能拼進(jìn)去，則哈希表全部清零，從下一個(gè)詞開始重新匹配。

Substring with Concatenation of All Words 
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.


For example, given: s: "barfoothefoobarman" words: ["foo", "bar"]


You should return the indices: [0,9].


(order does not matter).
哈希表計(jì)數(shù)法 復(fù)雜度

時(shí)間 O(NK) 空間 O(M)

思路

由于數(shù)組中所有單詞的長(zhǎng)度都是一樣的，我們可以像Longest Substring with At Most Two Distinct Characters中一樣，把每個(gè)詞當(dāng)作一個(gè)字母來(lái)看待，但是要遍歷K次，K是單詞的長(zhǎng)度，因?yàn)槲覀円謩e統(tǒng)計(jì)從下標(biāo)0開頭，從下標(biāo)1開頭。。。直到下標(biāo)K-1開頭的字符串。舉例來(lái)說(shuō)foobarfoo，給定數(shù)組是[foo, bar]，那我們要對(duì)foo|bar|foo搜索一次，對(duì)oob|arf|oo搜索一次，對(duì)oba|rfo|o搜索一次，我們不用再對(duì)bar|foo搜索，因?yàn)槠湟呀?jīng)包含在第一種里面了。每次搜索中，我們通過(guò)哈希表維護(hù)一個(gè)窗口，比如foo|bar|foo中，我們先拿出foo。如果foo都不在數(shù)組中，那說(shuō)明根本不能拼進(jìn)去，則哈希表全部清零，從下一個(gè)詞開始重新匹配。但是foo是在數(shù)組中的，所以給當(dāng)前搜索的哈希表計(jì)數(shù)器加上1，如果發(fā)現(xiàn)當(dāng)前搜索中foo出現(xiàn)的次數(shù)已經(jīng)比給定數(shù)組中foo出現(xiàn)的次數(shù)多了，我們就要把上一次出現(xiàn)foo之前的所有詞都從窗口中去掉，如果沒(méi)有更多，則看下一個(gè)詞bar，不過(guò)在這之前，我們還要看看窗口中有多少個(gè)詞了，如果詞的個(gè)數(shù)等于數(shù)組中詞的個(gè)數(shù)，說(shuō)明我們找到了一個(gè)結(jié)果。

注意

先判斷輸入是否為空，為空直接返回空結(jié)果

代碼 
public class Solution {
    public List findSubstring(String s, String[] words) {
        List res = new LinkedList();
        if(words == null || words.length == 0 || s == null || s.equals("")) return res;
        HashMap freq = new HashMap();
        // 統(tǒng)計(jì)數(shù)組中每個(gè)詞出現(xiàn)的次數(shù)，放入哈希表中待用
        for(String word : words){
            freq.put(word, freq.containsKey(word) ? freq.get(word) + 1 : 1);
        }
        // 得到每個(gè)詞的長(zhǎng)度
        int len = words[0].length();
        // 錯(cuò)開位來(lái)統(tǒng)計(jì)
        for(int i = 0; i < len; i++){
            // 建一個(gè)新的哈希表，記錄本輪搜索中窗口內(nèi)單詞出現(xiàn)次數(shù)
            HashMap currFreq = new HashMap();
            // start是窗口的開始，count表明窗口內(nèi)有多少詞
            int start = i, count = 0;
            for(int j = i; j <= s.length() - len; j += len){
                String sub = s.substring(j, j + len);
                // 看下一個(gè)詞是否是給定數(shù)組中的
                if(freq.containsKey(sub)){
                    // 窗口中單詞出現(xiàn)次數(shù)加1
                    currFreq.put(sub, currFreq.containsKey(sub) ? currFreq.get(sub) + 1 : 1);
                    count++;
                    // 如果該單詞出現(xiàn)次數(shù)已經(jīng)超過(guò)給定數(shù)組中的次數(shù)了，說(shuō)明多來(lái)了一個(gè)該單詞，所以要把窗口中該單詞上次出現(xiàn)的位置及之前所有單詞給去掉
                    while(currFreq.get(sub) > freq.get(sub)){
                        String leftMost = s.substring(start, start + len);
                        currFreq.put(leftMost, currFreq.get(leftMost) - 1);
                        start = start + len;
                        count--;
                    }
                    // 如果窗口內(nèi)單詞數(shù)和總單詞數(shù)一樣，則找到結(jié)果
                    if(count == words.length){
                        String leftMost = s.substring(start, start + len);
                        currFreq.put(leftMost, currFreq.get(leftMost) - 1);
                        res.add(start);
                        start = start + len;
                        count--;
                    }
                // 如果截出來(lái)的單詞都不在數(shù)組中，前功盡棄，重新開始
                } else {
                    currFreq.clear();
                    start = j + len;
                    count = 0;
                }
            }
        }
        return res;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/64700.html

相關(guān)文章

  • leetcode30 Substring with Concatenation of All Wor

    摘要：同時(shí)利用來(lái)存儲(chǔ)當(dāng)前結(jié)果值所在的起始下標(biāo)。然而，一旦出現(xiàn)重復(fù)值后，例如輸入的為，則無(wú)法判斷當(dāng)前重復(fù)值是否應(yīng)當(dāng)在結(jié)果集中。如果中的元素都被清空，則代表該子數(shù)組符合要求，即將起始下標(biāo)添加進(jìn)入結(jié)果集。利用左右指針來(lái)限定最小子數(shù)組的范圍，即窗口大小。 題目要求 You are given a string, s, and a list of words, words, that are all ...

    Y3G 評(píng)論0 收藏0

  • [leetcode] Minimum Window Substring

    摘要：使用而不是因?yàn)槲覀冃枰氖亲钪?，中間值我們不在乎，所以一次收斂到最小。下面來(lái)三個(gè)需要查重并且記錄上次出現(xiàn)的位置，選擇以為例，走到用做檢查，發(fā)現(xiàn)出現(xiàn)過(guò)，把移到的下一個(gè)。是上個(gè)題目的簡(jiǎn)易版，或者特殊版。 這里聊一聊解一類問(wèn)題，就是滿足某一條件的substring最值問(wèn)題。最開始我們以Minimum Window Substring為例，并整理總結(jié)leetcode里所有類似題目的通解。 Gi...

    Pines_Cheng 評(píng)論0 收藏0

  • [LeetCode] 336. Palindrome Pairs

    Problem Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome. Example 1: Inpu...

    lentoo 評(píng)論0 收藏0

  • [LeetCode]Find All Anagrams in a String

    摘要：解題思路，就是只順序不同但個(gè)數(shù)相同的字符串，那我們就可以利用的思想來(lái)比較每個(gè)字符串中字符出現(xiàn)的個(gè)數(shù)是否相等。 Find All Anagrams in a StringGiven a string s and a non-empty string p, find all the start indices of ps anagrams in s. Strings consists of...

    niceforbear 評(píng)論0 收藏0

  • leetcode438. Find All Anagrams in a String

    摘要：題目要求思路和代碼這是一個(gè)簡(jiǎn)單的雙指針問(wèn)題，即左指針指向可以作為起點(diǎn)的子數(shù)組下標(biāo)，右指針則不停向右移動(dòng)，將更多的元素囊括進(jìn)來(lái)，從而確保該左右指針內(nèi)的元素是目標(biāo)數(shù)組的一個(gè)兄弟子數(shù)組即每個(gè)字母的個(gè)數(shù)均相等左指針記錄每個(gè)字母出現(xiàn)的次數(shù)拷貝一個(gè) 題目要求 Given a string s and a non-empty string p, find all the start indices ...

    wangbinke 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<