[LintCode] Substring Anagrams

andong777 发布于2019-08-15 13:24 / 1056人阅读

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;
    }
}

云服务器 GPU云服务器 Anagrams LintCode LintCode134_LRU Substring

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

转载请注明本文地址：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 2019-08-14 15:22 评论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 2019-08-14 15:22 评论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
[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