资讯专栏INFORMATION COLUMN

[LintCode] Substring Anagrams

andong777 / 868人阅读

Problem

Given a string s and a non-empty string p, find all the start indices of p"s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 40,000.

The order of output does not matter.

Example

Given s = "cbaebabacd" p = "abc"

return [0, 6]

The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Solution
public class Solution {
    public List findAnagrams(String s, String p) {
    
        List res = new ArrayList<>();
        if (s == null || p == null || s.length() < p.length()) return res;
        
        //since it"s all lowercase English letters
        int[] sum = new int[26];
        for (char ch: p.toCharArray()) {
            sum[ch-"a"]++;
        }
        
        //build a sliding window
        int start = 0, end = 0, matched = 0;
        while (end < s.length()) {
            int index = s.charAt(end) - "a";
            if (sum[index] > 0) {
                matched++;
            } 
            sum[index]--;
            end++;
            //once the number of matched equals to p.length(), add the start index to result
            if (matched == p.length()) {
                res.add(start);
            }
            
            //move the window forward, restore `sum`
            if (end-start == p.length()) {
                if (sum[s.charAt(start)-"a"] >= 0) {
                    matched--;
                }
                sum[s.charAt(start)-"a"]++;
                start++;
            }
        }
        
        return res;
    }
}

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

转载请注明本文地址:https://www.ucloud.cn/yun/68074.html

相关文章

  • [LintCode] Anagrams

    摘要:对变形词的查找和归类,可以将自然排序的词根和所有同根变形词成对存入哈希表里。然后,返回里大于的字符串数组,再存入结果数组。注意并不是的结构,而是和数组相同的,所以存到一定要用方法。有几行容易出错的语句,可以注意一下 Problem Given an array of strings, return all groups of strings that are anagrams. Not...

    GitChat 评论0 收藏0
  • [LintCode/LeetCode] Two Strings are Anagrams/Valid

    摘要:建立一个长度为的数组,统计所有个字符在出现的次数,然后减去这些字符在中出现的次数。否则,循环结束,说明所有字符在和中出现的次数一致,返回。 Program Write a method anagram(s,t) to decide if two strings are anagrams or not. Example Given s=abcd, t=dcab, return true....

    vslam 评论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
  • [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 评论0 收藏0

发表评论

0条评论

andong777

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<