План курса / Все задачи / Алгоритмы и структуры данных
Удаление смайликов
легко
# решено
Дан массив символов chars. Нужно удалить из него все смайлики, подпадающие под регулярку :-\)+|:-\(+, и вернуть изменённый массив. Смайлики, образовавшиеся после удаления других, удалять не нужно.
Ввод: chars = [":","-",":","-",")",")","("]
Вывод: [":","-","("]
Объяснение: Смайлик образовался после удаления другого смайлика, поэтому его удалять не нужно
Ограничения:
len(chars) >= 1
chars содержит только ascii символы
public class Solution {
// Проверяем - является ли последовательность смайликом
private static bool IsSmile(List<char> chars, int p2) {
return p2 + 2 < chars.Count &&
chars[p2] == ':' &&
chars[p2 + 1] == '-' &&
(chars[p2 + 2] == '(' || chars[p2 + 2] == ')');
}
public static List<char> RemoveSmiles(List<char> chars) {
int p1 = 0;
int p2 = 0;
while (p2 < chars.Count) {
if (!IsSmile(chars, p2)) {
// Копируем текущий символ на позицию p1
chars[p1] = chars[p2];
p1++;
p2++;
continue;
}
// Пропускаем смайлик: начинаем с символа после :-?
char bracket = chars[p2 + 2];
p2 += 3;
while (p2 < chars.Count && chars[p2] == bracket) {
p2++;
}
}
return chars.GetRange(0, p1);
}
}
#include <vector>
using namespace std;
bool isSmile(vector<char> &chars, int p2) {
return p2 + 2 < chars.size() &&
chars[p2] == ':' &&
chars[p2 + 1] == '-' &&
(chars[p2 + 2] == '(' || chars[p2 + 2] == ')');
}
vector<char> removeSmiles(vector<char> &chars) {
int p1 = 0;
int p2 = 0;
while (p2 < chars.size()) {
if (!isSmile(chars, p2)) {
// Копируем текущий символ на позицию p1
chars[p1] = chars[p2];
p1++;
p2++;
continue;
}
// Пропускаем смайлик: начинаем с символа после :-?
char bracket = chars[p2 + 2];
p2 += 3;
while (p2 < chars.size() && chars[p2] == bracket) {
p2++;
}
}
return vector<char>(chars.begin(), chars.begin() + p1);
}
import java.util.*;
public class Solution {
// Проверяем - является ли последовательность смайликом
private boolean isSmile(List<Character> chars, int p2) {
return p2 + 2 < chars.size() &&
chars.get(p2) == ':' &&
chars.get(p2 + 1) == '-' &&
Set.of('(', ')').contains(chars.get(p2 + 2));
}
public List<Character> removeSmiles(List<Character> chars) {
int p1 = 0;
int p2 = 0;
while (p2 < chars.size()) {
if (!isSmile(chars, p2)) {
// Копируем текущий символ на позицию p1
chars.set(p1, chars.get(p2));
p1++;
p2++;
continue;
}
// Пропускаем смайлик: начинаем с символа после :-?
char bracket = chars.get(p2 + 2);
p2 += 3;
while (p2 < chars.size() && chars.get(p2) == bracket) {
p2++;
}
}
return chars.subList(0, p1);
}
}
from typing import *
def is_smile(chars: List[str], p2: int) -> bool:
return p2 + 2 < len(chars) and \
chars[p2] == ':' and \
chars[p2 + 1] == '-' and \
chars[p2 + 2] in {'(', ')'}
def remove_smiles(chars: List[str]) -> List[str]:
p1 = 0
p2 = 0
while p2 < len(chars):
if not is_smile(chars, p2):
# Копируем текущий символ на позицию p1
chars[p1] = chars[p2]
p1 += 1
p2 += 1
continue
# Пропускаем смайлик: начинаем с символа после :-?
bracket = chars[p2 + 2]
p2 += 3
while p2 < len(chars) and chars[p2] == bracket:
p2 += 1
return chars[:p1]
/**
* Проверяем - является ли последовательность смайликом
* @param {string[]} chars
* @param {number} p2
* @returns {boolean}
*/
function isSmile(chars, p2) {
return p2 + 2 < chars.length &&
chars[p2] === ':' &&
chars[p2 + 1] === '-' &&
(chars[p2 + 2] === '(' || chars[p2 + 2] === ')');
}
/**
* @param {string[]} chars
* @returns {string[]}
*/
export function removeSmiles(chars) {
let p1 = 0;
let p2 = 0;
while (p2 < chars.length) {
if (!isSmile(chars, p2)) {
// Копируем текущий символ на позицию p1
chars[p1] = chars[p2];
p1++;
p2++;
continue;
}
// Пропускаем смайлик: начинаем с символа после :-?
let bracket = chars[p2 + 2];
p2 += 3;
while (p2 < chars.length && chars[p2] === bracket) {
p2++;
}
}
return chars.slice(0, p1);
}
Оценка сложности
Время: O(n), где n - длина chars
Память: O(1)
Примечание: условие намеренно содержит регулярное выражение. Часть задания — догадаться, что использовать регулярку не нужно, так как требуется линейное время и ручная реализация алгоритма. Если кандидат сразу тянется к re.sub или аналогам — это red flag.
P.S. Если перефразировать задачу, то нужно удалить все смайлики вида :-) и :-( с произвольным числом скобок на конце.
Видео не скачано: Unknown video type or protected stream. Оригинальная ссылка