[Algo] Anagram Substring Search 变形词子串

Channe 发布于2019-08-14 12:45 / 725人阅读

摘要：统计字母频率复杂度时间空间思路用一个位的数组统计字符串中每一个字符出现的次数，然后同理，维护一个长度为长度的窗口，来统计这个窗口里母串各个字符出现的次数，计入一个数组中。比较这两个数组是否相同就知道是否是变形词子串了。

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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