438. Find All Anagrams in a String
LeetCode
medium
оригинал: C#
#array
#csharp
#hash-table
#leetcode
#medium
#search
#sliding-window
#string
#tree
Даны две строки s и p, вернуть массив всех начальных индексов анаграмм строки p в строке s. Ответ можно вернуть в любом порядке.
Анаграмма - это слово или фраза, образованные перестановкой букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз.
Пример:
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
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".
C# решение
сопоставлено/оригиналpublic class Solution {
public IList<int> FindAnagrams(string s, string p) {
int ns = s.Length, np = p.Length;
if (ns < np) return new List<int>();
var pCount = new Dictionary<char, int>();
var sCount = new Dictionary<char, int>();
foreach (char ch in p) {
if (pCount.ContainsKey(ch)) {
pCount[ch]++;
} else {
pCount[ch] = 1;
}
}
var output = new List<int>();
for (int i = 0; i < ns; ++i) {
char ch = s[i];
if (sCount.ContainsKey(ch)) {
sCount[ch]++;
} else {
sCount[ch] = 1;
}
if (i >= np) {
ch = s[i - np];
if (sCount[ch] == 1) {
sCount.Remove(ch);
} else {
sCount[ch]--;
}
}
if (pCount.SequenceEqual(sCount)) {
output.Add(i - np + 1);
}
}
return output;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public vector<int> FindAnagrams(string s, string p) {
int ns = s.size(), np = p.size();
if (ns < np) return new List<int>();
var pCount = new unordered_map<char, int>();
var sCount = new unordered_map<char, int>();
foreach (char ch in p) {
if (pCount.count(ch)) {
pCount[ch]++;
} else {
pCount[ch] = 1;
}
}
var output = new List<int>();
for (int i = 0; i < ns; ++i) {
char ch = s[i];
if (sCount.count(ch)) {
sCount[ch]++;
} else {
sCount[ch] = 1;
}
if (i >= np) {
ch = s[i - np];
if (sCount[ch] == 1) {
sCount.Remove(ch);
} else {
sCount[ch]--;
}
}
if (pCount.SequenceEqual(sCount)) {
output.push_back(i - np + 1);
}
}
return output;
}
}Java решение
сопоставлено/оригиналclass Solution {
public List<Integer> findAnagrams(String s, String p) {
int ns = s.length(), np = p.length();
if (ns < np) return new ArrayList<>();
Map<Character, Integer> pCount = new HashMap<>();
Map<Character, Integer> sCount = new HashMap<>();
for (char ch : p.toCharArray()) {
pCount.put(ch, pCount.getOrDefault(ch, 0) + 1);
}
List<Integer> output = new ArrayList<>();
for (int i = 0; i < ns; ++i) {
char ch = s.charAt(i);
sCount.put(ch, sCount.getOrDefault(ch, 0) + 1);
if (i >= np) {
ch = s.charAt(i - np);
if (sCount.get(ch) == 1) {
sCount.remove(ch);
} else {
sCount.put(ch, sCount.get(ch) - 1);
}
}
if (pCount.equals(sCount)) {
output.add(i - np + 1);
}
}
return output;
}
}JavaScript решение
сопоставлено/оригиналvar findAnagrams = function(s, p) {
let ns = s.length, np = p.length;
if (ns < np) return [];
let pCount = new Map();
let sCount = new Map();
for (let ch of p) {
pCount.set(ch, (pCount.get(ch) || 0) + 1);
}
let output = [];
for (let i = 0; i < ns; ++i) {
let ch = s[i];
sCount.set(ch, (sCount.get(ch) || 0) + 1);
if (i >= np) {
ch = s[i - np];
if (sCount.get(ch) === 1) {
sCount.delete(ch);
} else {
sCount.set(ch, sCount.get(ch) - 1);
}
}
if (pCount.size === sCount.size && Array.from(pCount.keys()).every(k => pCount.get(k) === sCount.get(k))) {
output.push(i - np + 1);
}
}
return output;
};Python решение
сопоставлено/оригиналclass Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
ns, np = len(s), len(p)
if ns < np:
return []
pCount = Counter(p)
sCount = Counter()
output = []
for i in range(ns):
sCount[s[i]] += 1
if i >= np:
if sCount[s[i - np]] == 1:
del sCount[s[i - np]]
else:
sCount[s[i - np]] -= 1
if pCount == sCount:
output.append(i - np + 1)
return outputGo решение
сопоставлено/оригиналfunc findAnagrams(s string, p string) []int {
ns, np := len(s), len(p)
if ns < np {
return []int{}
}
pCount := make(map[rune]int)
sCount := make(map[rune]int)
for _, ch := range p {
pCount[ch]++
}
output := []int{}
for i, ch := range s {
sCount[ch]++
if i >= np {
leftChar := rune(s[i-np])
if sCount[leftChar] == 1 {
delete(sCount, leftChar)
} else {
sCount[leftChar]--
}
}
if reflect.DeepEqual(pCount, sCount) {
output = append(output, i-np+1)
}
}
return output
}Algorithm
Построить эталонный счетчик pCount для строки p.
Передвигать скользящее окно по строке s: Пересчитывать счетчик скользящего окна sCount на каждом шаге, добавляя одну букву справа и удаляя одну букву слева.
Если sCount == pCount, обновить выходной список. Вернуть выходной список.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.
Активных вакансий пока нет.