Сегодня у нас еще одна задача на аккуратное манипулирование индексами 2337. Move Pieces to Obtain a String.
Описание задачи
Даны две строки start и target длины n, содержащие символы 'L', 'R' и '_'.
- Символ
'L' может двигаться только влево, если есть пустое место ('_') слева.
- Символ
'R' может двигаться только вправо, если есть пустое место ('_') справа.
- Необходимо определить, можно ли преобразовать строку
start в строку target с соблюдением этих правил.
Идея 🧠
Задача сводится к тому, чтобы проверить, совпадают ли позиции и направления символов 'L' и 'R' в двух строках с учётом их ограничений на движение. Мы используем итерацию по строкам одновременно, отслеживая доступные символы 'L' и 'R' через счётчики.
Подход 🛠️
- Используем метод
as_bytes(), чтобы быстро перебрать символы в виде байтов.
- Одновременно проходим по обеим строкам:
- Если видим
'L' в target, увеличиваем счётчик доступных 'L'.
- Если видим
'L' в start, проверяем, есть ли доступный 'L', и уменьшаем счётчик.
- Аналогично для
'R'
- Также проверяем, что
'R' не пересекает 'L', и аккуратно в правильном порядке синхронизируем счётчики.
- В конце проверяем, что все
'L' и 'R' учтены (баланс счётчиков нулевой).
Сложность 📊
- Временная сложность:
O(n) – один проход по строкам.
- Пространственная сложность:
O(1) – используем только два счётчика.
Такое решение минимизирует затраты времени и памяти, идеально подходя для больших строк.
Исходный код решения
impl Solution {
pub fn can_change(start: String, target: String) -> bool {
let mut left_pieces = 0; // Tracks available 'L' pieces
let mut right_pieces = 0; // Tracks available 'R' pieces
for (&start_char, &target_char) in
start.as_bytes().iter().zip(target.as_bytes().iter()
) {
// Check for target_char == 'L'
if target_char == b'L' {
if right_pieces > 0 {
return false; // 'L' cannot cross 'R'
}
left_pieces += 1;
}
// Check for start_char == 'L'
if start_char == b'L' {
if left_pieces <= 0 {
return false; // No available 'L' to move
}
left_pieces -= 1;
}
// Check for start_char == 'R'
if start_char == b'R' {
if left_pieces > 0 {
return false; // 'R' cannot cross 'L'
}
right_pieces += 1;
}
// Check for target_char == 'R'
if target_char == b'R' {
if right_pieces <= 0 {
return false; // 'R' must have a matching piece
}
right_pieces -= 1;
}
}
// All pieces should be accounted for
left_pieces == 0 && right_pieces == 0
}
}
Полезное замечание
- Порядок проверок в нашем коде значим и его изменение легко может привести к потере правильности кода.
- В продакшн системах такое обязательно нужно помечать и покрывать тестами, чтобы любители рефакторинга код не сломали
опять же поделюс своим решением тоже!
хотя оно не такое оптимальное судя по всему)
use std::iter::zip;
impl Solution {
pub fn can_change(start: String, target: String) -> bool {
{
let s1 = start.chars().filter(|it| *it != '_').collect::<String>();
let s2 = target.chars().filter(|it| *it != '_').collect::<String>();
if s1 != s2 {
return false;
}
};
let lindices1 = Self::collect(&start, 'L');
let rincides1 = Self::collect(&start, 'R');
let lindices2 = Self::collect(&target, 'L');
let rindices2 = Self::collect(&target, 'R');
for (l1, l2) in zip(lindices1, lindices2){
if l1 <= l2{
return false
}
}
for (r1, r2) in zip(rincides1, rindices2){
if r1 >= r2{
return false
}
}
true
}
fn collect(s:&str, target:char)->Vec<usize>{
s.char_indices().filter(|(_, ch)|*ch == 'L').map(|it|it.0).collect()
}
}