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.
ExampleGiven 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".
public class Solution { public ListfindAnagrams(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
摘要:对变形词的查找和归类,可以将自然排序的词根和所有同根变形词成对存入哈希表里。然后,返回里大于的字符串数组,再存入结果数组。注意并不是的结构,而是和数组相同的,所以存到一定要用方法。有几行容易出错的语句,可以注意一下 Problem Given an array of strings, return all groups of strings that are anagrams. Not...
摘要:建立一个长度为的数组,统计所有个字符在出现的次数,然后减去这些字符在中出现的次数。否则,循环结束,说明所有字符在和中出现的次数一致,返回。 Program Write a method anagram(s,t) to decide if two strings are anagrams or not. Example Given s=abcd, t=dcab, return true....
摘要:解题思路,就是只顺序不同但个数相同的字符串,那我们就可以利用的思想来比较每个字符串中字符出现的个数是否相等。 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...
摘要:题目要求思路和代码这是一个简单的双指针问题,即左指针指向可以作为起点的子数组下标,右指针则不停向右移动,将更多的元素囊括进来,从而确保该左右指针内的元素是目标数组的一个兄弟子数组即每个字母的个数均相等左指针记录每个字母出现的次数拷贝一个 题目要求 Given a string s and a non-empty string p, find all the start indices ...
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...
阅读 1154·2021-11-23 09:51
阅读 1951·2021-10-08 10:05
阅读 2290·2019-08-30 15:56
阅读 1805·2019-08-30 15:55
阅读 2617·2019-08-30 15:55
阅读 2436·2019-08-30 13:53
阅读 3443·2019-08-30 12:52
阅读 1217·2019-08-29 10:57