国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[Leetcode] Substring with Concatenation of All Wor

adie / 354人閱讀

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

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

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

思路

由于數組中所有單詞的長度都是一樣的，我們可以像Longest Substring with At Most Two Distinct Characters中一樣，把每個詞當作一個字母來看待，但是要遍歷K次，K是單詞的長度，因為我們要分別統計從下標0開頭，從下標1開頭。。。直到下標K-1開頭的字符串。舉例來說foobarfoo，給定數組是[foo, bar]，那我們要對foo|bar|foo搜索一次，對oob|arf|oo搜索一次，對oba|rfo|o搜索一次，我們不用再對bar|foo搜索，因為其已經包含在第一種里面了。每次搜索中，我們通過哈希表維護一個窗口，比如foo|bar|foo中，我們先拿出foo。如果foo都不在數組中，那說明根本不能拼進去，則哈希表全部清零，從下一個詞開始重新匹配。但是foo是在數組中的，所以給當前搜索的哈希表計數器加上1，如果發現當前搜索中foo出現的次數已經比給定數組中foo出現的次數多了，我們就要把上一次出現foo之前的所有詞都從窗口中去掉，如果沒有更多，則看下一個詞bar，不過在這之前，我們還要看看窗口中有多少個詞了，如果詞的個數等于數組中詞的個數，說明我們找到了一個結果。

注意

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

代碼 
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();
        // 統計數組中每個詞出現的次數，放入哈希表中待用
        for(String word : words){
            freq.put(word, freq.containsKey(word) ? freq.get(word) + 1 : 1);
        }
        // 得到每個詞的長度
        int len = words[0].length();
        // 錯開位來統計
        for(int i = 0; i < len; i++){
            // 建一個新的哈希表，記錄本輪搜索中窗口內單詞出現次數
            HashMap currFreq = new HashMap();
            // start是窗口的開始，count表明窗口內有多少詞
            int start = i, count = 0;
            for(int j = i; j <= s.length() - len; j += len){
                String sub = s.substring(j, j + len);
                // 看下一個詞是否是給定數組中的
                if(freq.containsKey(sub)){
                    // 窗口中單詞出現次數加1
                    currFreq.put(sub, currFreq.containsKey(sub) ? currFreq.get(sub) + 1 : 1);
                    count++;
                    // 如果該單詞出現次數已經超過給定數組中的次數了，說明多來了一個該單詞，所以要把窗口中該單詞上次出現的位置及之前所有單詞給去掉
                    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--;
                    }
                    // 如果窗口內單詞數和總單詞數一樣，則找到結果
                    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--;
                    }
                // 如果截出來的單詞都不在數組中，前功盡棄，重新開始
                } else {
                    currFreq.clear();
                    start = j + len;
                    count = 0;
                }
            }
        }
        return res;
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64700.html

相關文章

  • leetcode30 Substring with Concatenation of All Wor

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

    Y3G 評論0 收藏0

  • [leetcode] Minimum Window Substring

    摘要：使用而不是因為我們需要的是最值，中間值我們不在乎，所以一次收斂到最小。下面來三個需要查重并且記錄上次出現的位置，選擇以為例，走到用做檢查，發現出現過，把移到的下一個。是上個題目的簡易版，或者特殊版。 這里聊一聊解一類問題，就是滿足某一條件的substring最值問題。最開始我們以Minimum Window Substring為例，并整理總結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

    摘要：解題思路，就是只順序不同但個數相同的字符串，那我們就可以利用的思想來比較每個字符串中字符出現的個數是否相等。 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

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

    wangbinke 評論0 收藏0

發表評論

0條評論

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