[Algo] Anagram Substring Search 變形詞子串

Channe 發(fā)布于2019-08-14 12:45 / 732人閱讀

摘要：統(tǒng)計字母頻率復雜度時間空間思路用一個位的數(shù)組統(tǒng)計字符串中每一個字符出現(xiàn)的次數(shù)，然后同理，維護一個長度為長度的窗口，來統(tǒng)計這個窗口里母串各個字符出現(xiàn)的次數(shù)，計入一個數(shù)組中。比較這兩個數(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)計字母頻率 復雜度

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

思路

用一個256位的數(shù)組統(tǒng)計Pattern字符串中每一個字符出現(xiàn)的次數(shù)，然后同理，維護一個長度為Pattern長度的窗口，來統(tǒng)計這個窗口里母串各個字符出現(xiàn)的次數(shù)，計入一個數(shù)組中。比較這兩個數(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();
        // 一個數(shù)組統(tǒng)計Pattern的字符出現(xiàn)次數(shù)
        int[] pntcnt = new int[256];
        // 一個數(shù)字統(tǒng)計窗口內(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()){
            // 新來一個字符，自增其出現(xiàn)次數(shù)
            strcnt[str.charAt(i)]++;
            // 將離開窗口的字符次數(shù)減一
            strcnt[str.charAt(i - ptn.length())]--;
            i++;
            // 判斷兩個數(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;
    }
}

云服務器 GPU云服務器詞子串 Algo Anagram Substring

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

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

[Leetcode] Valid Anagram 驗證變形詞

摘要：排序法復雜度時間空間思路因為變形詞兩個單詞對應字母出現(xiàn)的次數(shù)都相同，所以如果將兩個單詞按字母順序排序，肯定會變?yōu)橐粋€字符串，如果字符串不相同，則不是變形詞。 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 2019-08-14 12:38 評論0 收藏0
JavaScript字符串操作方法大全，包含ES6方法

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

Scorpion 2019-08-23 12:14 評論0 收藏0
[LeetCode] 438. Find All Anagrams in a String [滑動窗

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 2019-08-19 11:18 評論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 2019-08-16 10:26 評論0 收藏0
leetcode438. Find All Anagrams in a String

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

wangbinke 2019-08-16 17:50 評論0 收藏0