[Algo] Anagram Substring Search 變形詞子串

Channe 發布于2019-08-14 12:45 / 731人閱讀

摘要：統計字母頻率復雜度時間空間思路用一個位的數組統計字符串中每一個字符出現的次數，然后同理，維護一個長度為長度的窗口，來統計這個窗口里母串各個字符出現的次數，計入一個數組中。比較這兩個數組是否相同就知道是否是變形詞子串了。

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

統計字母頻率 復雜度

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

思路

用一個256位的數組統計Pattern字符串中每一個字符出現的次數，然后同理，維護一個長度為Pattern長度的窗口，來統計這個窗口里母串各個字符出現的次數，計入一個數組中。比較這兩個數組是否相同就知道是否是變形詞子串了。窗口向右移動一位時，加上新來的字符，減去剛離開窗口的字符。

代碼

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();
        // 一個數組統計Pattern的字符出現次數
        int[] pntcnt = new int[256];
        // 一個數字統計窗口內的字符出現次數
        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()){
            // 新來一個字符，自增其出現次數
            strcnt[str.charAt(i)]++;
            // 將離開窗口的字符次數減一
            strcnt[str.charAt(i - ptn.length())]--;
            i++;
            // 判斷兩個數組是否相同
            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

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

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

[Leetcode] Valid Anagram 驗證變形詞

摘要：排序法復雜度時間空間思路因為變形詞兩個單詞對應字母出現的次數都相同，所以如果將兩個單詞按字母順序排序，肯定會變為一個字符串，如果字符串不相同，則不是變形詞。 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方法

摘要：要執行忽略大小寫的檢索，請追加標志。八提取字符串的片斷，并在新的字符串中返回被提取的部分。九把字符串分割為字符串數組。十一把字符串轉換為大寫。十四從起始索引號提取字符串中指定數目的字符。。子串中的字符數。新增的操作字符串的方法一一、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

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

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

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