План курса / Все задачи / Алгоритмы и структуры данных
Поиск мутирующего вируса
средне
# решено
Необходимо вернуть true, если в строке gene встречается строка virus или любая другая строка, которая является пермутацией строки virus.
Пермутацией строки называется любая перестановка ее букв. Например, для строки "abb" пермутациями будут "bab" и "bba".
Пример 1:
Ввод: gene = "cdeebba", virus = "abb"
Вывод: true
Объяснение: нужно проверить, есть ли в строке "cdeebba" подстрока "abb" или "bab" или "bba". Есть подстрока "bba", поэтому вернем true.
Строка gene и строка virus могут содержать только английские буквы
using System;
using System.Collections.Generic;
public class Solution {
public static bool CheckForVirus(string gene, string virus) {
Dictionary<char, int> virusGene = new Dictionary<char, int>();
foreach (char ch in virus) {
if (!virusGene.ContainsKey(ch))
virusGene[ch] = 0;
virusGene[ch]++;
}
int l = 0;
int r = -1;
Dictionary<char, int> windowGene = new Dictionary<char, int>();
while (l < gene.Length) {
while (r + 1 < gene.Length &&
virusGene.ContainsKey(gene[r + 1]) &&
(!windowGene.ContainsKey(gene[r + 1]) || windowGene[gene[r + 1]] + 1 <= virusGene[gene[r + 1]]))
{
char ch = gene[r + 1];
if (!windowGene.ContainsKey(ch))
windowGene[ch] = 0;
windowGene[ch]++;
r++;
}
// обновляем ответ
int windowSize = r - l + 1;
if (windowSize == virus.Length)
return true;
// двигаем левый указатель
char leftChar = gene[l];
if (!windowGene.ContainsKey(leftChar))
windowGene[leftChar] = 0;
windowGene[leftChar]--;
if (windowGene[leftChar] == 0) {
windowGene.Remove(leftChar);
} else if (windowGene[leftChar] < 0) {
windowGene.Remove(leftChar);
r = l;
}
l++;
}
return false;
}
}
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
bool checkForVirus(string &gene, string &virus)
{
unordered_map<char, int> virusGene;
for (char ch : virus) {
virusGene[ch]++;
}
int l = 0;
int r = -1;
unordered_map<char, int> windowGene;
while (l < gene.size()) {
while (r + 1 < gene.size() &&
virusGene.count(gene[r + 1]) &&
windowGene[gene[r + 1]] + 1 <= virusGene[gene[r + 1]])
{
windowGene[gene[r + 1]]++;
r++;
}
int windowSize = r - l + 1;
if (windowSize == virus.size()) {
return true;
}
windowGene[gene[l]]--;
if (windowGene[gene[l]] == 0) {
windowGene.erase(gene[l]);
} else if (windowGene[gene[l]] < 0) {
windowGene.erase(gene[l]);
r = l;
}
l++;
}
return false;
}
package main
func checkForVirus(gene string, virus string) bool {
virusGene := map[byte]int{}
for i := 0; i < len(virus); i++ {
virusGene[virus[i]]++
}
l := 0
r := -1
windowGene := map[byte]int{}
for l < len(gene) {
for r+1 < len(gene) && virusGene[gene[r+1]] > 0 && windowGene[gene[r+1]]+1 <= virusGene[gene[r+1]] {
windowGene[gene[r+1]]++
r++
}
windowSize := r - l + 1
if windowSize == len(virus) {
return true
}
windowGene[gene[l]]--
if windowGene[gene[l]] == 0 {
delete(windowGene, gene[l])
} else if windowGene[gene[l]] < 0 {
delete(windowGene, gene[l])
r = l
}
l++
}
return false
}
import java.util.*;
public class Solution {
private static <K, V> V getOrDefault(Map<K,V> map, K key, V defaultValue) {
return map.containsKey(key) ? map.get(key) : defaultValue;
}
public boolean checkForVirus(String gene, String virus) {
HashMap<Character, Integer> virusGene = new HashMap();
for (int i = 0; i < virus.length(); i++) {
virusGene.merge(virus.charAt(i), 1, Integer::sum);
}
int l = 0;
int r = -1;
HashMap<Character, Integer> windowGene = new HashMap();
while (l < gene.length()) {
while (r + 1 < gene.length() && getOrDefault(windowGene, gene.charAt(r + 1), 0) + 1 <= getOrDefault(virusGene, gene.charAt(r + 1), 0)) {
windowGene.merge(gene.charAt(r + 1), 1, Integer::sum);
r += 1;
}
int windowSize = r - l + 1;
if (virus.length() == windowSize) {
return true;
}
windowGene.merge(gene.charAt(l), -1, Integer::sum);
if (windowGene.get(gene.charAt(l)) == 0) {
windowGene.remove(gene.charAt(l));
} else if (windowGene.get(gene.charAt(l)) < 0) {
windowGene.remove(gene.charAt(l));
r = l;
}
l = l + 1;
}
return false;
}
}
import java.util.*;
public class Solution {
private static <K, V> V getOrDefault(Map<K,V> map, K key, V defaultValue) {
return map.containsKey(key) ? map.get(key) : defaultValue;
}
public boolean checkForVirus(String gene, String virus) {
HashMap<Character, Integer> virusGene = new HashMap();
for (int i = 0; i < virus.length(); i++) {
virusGene.merge(virus.charAt(i), 1, Integer::sum);
}
int l = 0;
int r = -1;
HashMap<Character, Integer> windowGene = new HashMap();
while (l < gene.length()) {
while (r + 1 < gene.length() && getOrDefault(windowGene, gene.charAt(r + 1), 0) + 1 <= getOrDefault(virusGene, gene.charAt(r + 1), 0)) {
windowGene.merge(gene.charAt(r + 1), 1, Integer::sum);
r += 1;
}
int windowSize = r - l + 1;
if (virus.length() == windowSize) {
return true;
}
windowGene.merge(gene.charAt(l), -1, Integer::sum);
if (windowGene.get(gene.charAt(l)) == 0) {
windowGene.remove(gene.charAt(l));
} else if (windowGene.get(gene.charAt(l)) < 0) {
windowGene.remove(gene.charAt(l));
r = l;
}
l = l + 1;
}
return false;
}
}
from typing import *
from collections import defaultdict
def check_for_virus(gene: str, virus: str) -> bool:
virusGene = defaultdict(int)
for ch in virus:
virusGene[ch] += 1
l = 0
r = -1
windowGene = defaultdict(int)
while l < len(gene):
while r + 1 < len(gene) and windowGene[gene[r + 1]] + 1 <= virusGene[gene[r + 1]]:
windowGene[gene[r + 1]] += 1
r += 1
windowSize = r - l + 1
if len(virus) == windowSize:
return True
windowGene[gene[l]] -= 1
if windowGene[gene[l]] == 0:
del windowGene[gene[l]]
elif windowGene[gene[l]] < 0:
del windowGene[gene[l]]
r = l
l += 1
return False