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

資訊專欄INFORMATION COLUMN

[Algo] Anagram Substring Search 變形詞子串

Channe / 789人閱讀

摘要：統(tǒng)計(jì)字母頻率復(fù)雜度時(shí)間空間思路用一個(gè)位的數(shù)組統(tǒng)計(jì)字符串中每一個(gè)字符出現(xiàn)的次數(shù)，然后同理，維護(hù)一個(gè)長度為長度的窗口，來統(tǒng)計(jì)這個(gè)窗口里母串各個(gè)字符出現(xiàn)的次數(shù)，計(jì)入一個(gè)數(shù)組中。比較這兩個(gè)數(shù)組是否相同就知道是否是變形詞子串了。

Anagram Substring Search 
Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[]) that prints all occurrences of pat[] and its permutations (or anagrams) in txt[]. You may assume that n > m.


1) Input:  txt[] = "BACDGABCDA"  pat[] = "ABCD"
   Output:   Found at Index 0
             Found at Index 5
             Found at Index 6
2) Input: txt[] =  "AAABABAA" pat[] = "AABA"
   Output:   Found at Index 0
             Found at Index 1
             Found at Index 4
統(tǒng)計(jì)字母頻率 復(fù)雜度

時(shí)間 O(NM) 空間 O(1)

思路

用一個(gè)256位的數(shù)組統(tǒng)計(jì)Pattern字符串中每一個(gè)字符出現(xiàn)的次數(shù)，然后同理，維護(hù)一個(gè)長度為Pattern長度的窗口，來統(tǒng)計(jì)這個(gè)窗口里母串各個(gè)字符出現(xiàn)的次數(shù)，計(jì)入一個(gè)數(shù)組中。比較這兩個(gè)數(shù)組是否相同就知道是否是變形詞子串了。窗口向右移動(dòng)一位時(shí)，加上新來的字符，減去剛離開窗口的字符。

代碼 
public class AnagramSubstring {
    
    public static void main(String[] args){
        System.out.println(findSubstring("BACDGABCDA", "ABCD"));
        
    }
    
    public static List findSubstring(String str, String ptn){
        List res = new LinkedList();
        // 一個(gè)數(shù)組統(tǒng)計(jì)Pattern的字符出現(xiàn)次數(shù)
        int[] pntcnt = new int[256];
        // 一個(gè)數(shù)字統(tǒng)計(jì)窗口內(nèi)的字符出現(xiàn)次數(shù)
        int[] strcnt = new int[256];
        for(int i = 0; i < ptn.length(); i++){
            pntcnt[ptn.charAt(i)]++;
        }
        int i = 0;
        for(i = 0; i < ptn.length() && i < str.length(); i++){
            strcnt[str.charAt(i)]++;
        }
        if(isSame(pntcnt, strcnt)){
            res.add(i - ptn.length());
        }
        while(i < str.length()){
            // 新來一個(gè)字符，自增其出現(xiàn)次數(shù)
            strcnt[str.charAt(i)]++;
            // 將離開窗口的字符次數(shù)減一
            strcnt[str.charAt(i - ptn.length())]--;
            i++;
            // 判斷兩個(gè)數(shù)組是否相同
            if(isSame(pntcnt, strcnt)){
                res.add(i - ptn.length());
            }
        }
        return res;
    }
    
    public static boolean isSame(int[] arr1, int[] arr2){
        if(arr1.length != arr2.length) return false;
        for(int i = 0; i < arr1.length; i++){
            if(arr1[i] != arr2[i]) return false;
        }
        return true;
    }
}

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

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

相關(guān)文章

  • [Leetcode] Valid Anagram 驗(yàn)證變形詞

    摘要：排序法復(fù)雜度時(shí)間空間思路因?yàn)樽冃卧~兩個(gè)單詞對應(yīng)字母出現(xiàn)的次數(shù)都相同，所以如果將兩個(gè)單詞按字母順序排序，肯定會(huì)變?yōu)橐粋€(gè)字符串，如果字符串不相同，則不是變形詞。 Valid Anagram Given two strings s and t, write a function to determine if t is an anagram of s. For example, s = a...

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

  • JavaScript字符串操作方法大全，包含ES6方法

    摘要：要執(zhí)行忽略大小寫的檢索，請追加標(biāo)志。八提取字符串的片斷，并在新的字符串中返回被提取的部分。九把字符串分割為字符串?dāng)?shù)組。十一把字符串轉(zhuǎn)換為大寫。十四從起始索引號(hào)提取字符串中指定數(shù)目的字符。。子串中的字符數(shù)。新增的操作字符串的方法一 一、charAt() 返回在指定位置的字符。 var str=abc console.log(str.charAt(0))//a 二、charCodeAt(...

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

  • [LeetCode] 438. Find All Anagrams in a String [滑動(dòng)窗

    Problem Given a string s and a non-empty string p, find all the start indices of ps anagrams in s. Strings consists of lowercase English letters only and the length of both strings s and p will not be...

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

  • [LeetCode]Find All Anagrams in a String

    摘要：解題思路，就是只順序不同但個(gè)數(shù)相同的字符串，那我們就可以利用的思想來比較每個(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è)簡單的雙指針問題，即左指針指向可以作為起點(diǎn)的子數(shù)組下標(biāo)，右指針則不停向右移動(dòng)，將更多的元素囊括進(jìn)來，從而確保該左右指針內(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元查看
<