資訊專欄INFORMATION COLUMN
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 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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/68074.html
摘要：對(duì)變形詞的查找和歸類，可以將自然排序的詞根和所有同根變形詞成對(duì)存入哈希表里。然后，返回里大于的字符串?dāng)?shù)組，再存入結(jié)果數(shù)組。注意并不是的結(jié)構(gòu)，而是和數(shù)組相同的，所以存到一定要用方法。有幾行容易出錯(cuò)的語(yǔ)句，可以注意一下 Problem Given an array of strings, return all groups of strings that are anagrams. Not...
摘要：建立一個(gè)長(zhǎng)度為的數(shù)組，統(tǒng)計(jì)所有個(gè)字符在出現(xiàn)的次數(shù)，然后減去這些字符在中出現(xiàn)的次數(shù)。否則，循環(huán)結(jié)束，說(shuō)明所有字符在和中出現(xiàn)的次數(shù)一致，返回。 Program Write a method anagram(s,t) to decide if two strings are anagrams or not. Example Given s=abcd, t=dcab, return true....
摘要：解題思路，就是只順序不同但個(gè)數(shù)相同的字符串，那我們就可以利用的思想來(lái)比較每個(gè)字符串中字符出現(xiàn)的個(gè)數(shù)是否相等。 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...
摘要：題目要求思路和代碼這是一個(gè)簡(jiǎn)單的雙指針問(wèn)題，即左指針指向可以作為起點(diǎn)的子數(shù)組下標(biāo)，右指針則不停向右移動(dòng)，將更多的元素囊括進(jìn)來(lái)，從而確保該左右指針內(nèi)的元素是目標(biāo)數(shù)組的一個(gè)兄弟子數(shù)組即每個(gè)字母的個(gè)數(shù)均相等左指針記錄每個(gè)字母出現(xiàn)的次數(shù)拷貝一個(gè) 題目要求 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...
閱讀 1237·2021-11-23 09:51
閱讀 2015·2021-10-08 10:05
閱讀 2372·2019-08-30 15:56
閱讀 1926·2019-08-30 15:55
閱讀 2663·2019-08-30 15:55
閱讀 2511·2019-08-30 13:53
閱讀 3524·2019-08-30 12:52
閱讀 1281·2019-08-29 10:57
