🔄 Проверка преобразования строк с ограничениями на движение

leetcoder, 05-12-2024 ,

282

Сегодня у нас еще одна задача на аккуратное манипулирование индексами 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
    }
}

Полезное замечание

Порядок проверок в нашем коде значим и его изменение легко может привести к потере правильности кода.
В продакшн системах такое обязательно нужно помечать и покрывать тестами, чтобы любители рефакторинга код не сломали