成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Substring with Concatenation of All Wor

adie / 358人閱讀

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

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).
哈希表計數(shù)法 復(fù)雜度

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

思路

由于數(shù)組中所有單詞的長度都是一樣的，我們可以像Longest Substring with At Most Two Distinct Characters中一樣，把每個詞當(dāng)作一個字母來看待，但是要遍歷K次，K是單詞的長度，因為我們要分別統(tǒng)計從下標(biāo)0開頭，從下標(biāo)1開頭。。。直到下標(biāo)K-1開頭的字符串。舉例來說foobarfoo，給定數(shù)組是[foo, bar]，那我們要對foo|bar|foo搜索一次，對oob|arf|oo搜索一次，對oba|rfo|o搜索一次，我們不用再對bar|foo搜索，因為其已經(jīng)包含在第一種里面了。每次搜索中，我們通過哈希表維護(hù)一個窗口，比如foo|bar|foo中，我們先拿出foo。如果foo都不在數(shù)組中，那說明根本不能拼進(jìn)去，則哈希表全部清零，從下一個詞開始重新匹配。但是foo是在數(shù)組中的，所以給當(dāng)前搜索的哈希表計數(shù)器加上1，如果發(fā)現(xiàn)當(dāng)前搜索中foo出現(xiàn)的次數(shù)已經(jīng)比給定數(shù)組中foo出現(xiàn)的次數(shù)多了，我們就要把上一次出現(xiàn)foo之前的所有詞都從窗口中去掉，如果沒有更多，則看下一個詞bar，不過在這之前，我們還要看看窗口中有多少個詞了，如果詞的個數(shù)等于數(shù)組中詞的個數(shù)，說明我們找到了一個結(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)計數(shù)組中每個詞出現(xiàn)的次數(shù)，放入哈希表中待用
        for(String word : words){
            freq.put(word, freq.containsKey(word) ? freq.get(word) + 1 : 1);
        }
        // 得到每個詞的長度
        int len = words[0].length();
        // 錯開位來統(tǒng)計
        for(int i = 0; i < len; i++){
            // 建一個新的哈希表，記錄本輪搜索中窗口內(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);
                // 看下一個詞是否是給定數(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)超過給定數(shù)組中的次數(shù)了，說明多來了一個該單詞，所以要把窗口中該單詞上次出現(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--;
                    }
                // 如果截出來的單詞都不在數(shù)組中，前功盡棄，重新開始
                } else {
                    currFreq.clear();
                    start = j + len;
                    count = 0;
                }
            }
        }
        return res;
    }
}

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64700.html

相關(guān)文章

  • leetcode30 Substring with Concatenation of All Wor

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

    Y3G 評論0 收藏0

  • [leetcode] Minimum Window Substring

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

    Pines_Cheng 評論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 評論0 收藏0

  • [LeetCode]Find All Anagrams in a String

    摘要：解題思路，就是只順序不同但個數(shù)相同的字符串，那我們就可以利用的思想來比較每個字符串中字符出現(xiàn)的個數(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 評論0 收藏0

  • leetcode438. Find All Anagrams in a String

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

    wangbinke 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<