главная новое лучшее написать
▲
3
▼

Проверка возможности коррекции скобочной записи с использованием итераторов 🚀
leetcoder, 13-01-2025 , 145

Сегодня мы рассмотрим решение задачи 2116. Check if a Parentheses String Can Be Valid.

🧩 Описание задачи

Дана строка s, состоящая только из символов '(' и ')', и строка locked длины n, состоящая из символов '0' и '1'. Каждая позиция в locked указывает, можно ли изменить символ в s на этой позиции:

Нужно определить, можно ли сделать строку s корректной скобочной записью.

💡 Идея

Решение основывается на двух проходах по строке:
- Прямой проход: Проверяем баланс открывающих и закрывающих скобок слева направо, учитывая символы, которые можно менять.
- Обратный проход: Инвертируем строку (меняем '(' на ')' и наоборот) и проверяем баланс справа налево.

При каждом проходе используем два счётчика:
- balance для отслеживания текущего баланса скобок.
- free для отслеживания количества символов, которые можно изменить.

Если на любом этапе баланс становится отрицательным, и его нельзя компенсировать изменением свободных символов, строка не может быть сделана валидной.

🔧 Подробности подхода

  1. Прямой проход:
    • Проходим по строке слева направо, обновляя баланс и количество свободных символов.
    • Если баланс становится отрицательным, используем свободные символы для его восстановления. Если свободных символов недостаточно, строка невалидна.
  2. Обратный проход:
    • Инвертируем строку: меняем '(' на ')' и наоборот.
    • Проходим по строке справа налево с тем же алгоритмом.
  3. Итераторы:
    • Для упрощения логики используем итераторы для обработки строк. Прямой и обратный проходы оформлены как отдельные итераторы, которые генерируют пары (символ, locked).
  4. Крайний случай:
    • Строки нечётной длины нельзя сделать корректными ни при каких условиях.

⏱️ Асимптотика

📝 Исходный код

impl Solution {
    pub fn can_be_valid(s: String, locked: String) -> bool {
        if s.len() % 2 != 0 {
            return false;
        }

        let s_bytes = s.as_bytes();
        let locked_bytes = locked.as_bytes();

        // Forward pass iterator
        let forward_iter = s_bytes.iter().zip(locked_bytes.iter());

        // Forward pass
        if !Self::check_balance(forward_iter) {
            return false;
        }

        // Backward pass iterator
        let backward_iter = s_bytes.iter().rev()
            .zip(locked_bytes.iter().rev())
            .map(|(char, lock)| {
                let swapped_char = if *char == b'(' { &b')' } else { &b'(' };
                (swapped_char, lock)
            });

        // Backward pass
        if !Self::check_balance(backward_iter) {
            return false;
        }

        true
    }

    fn check_balance<'a>(iter: impl Iterator<Item = (&'a u8, &'a u8)>) -> bool {
        let mut balance = 0;
        let mut free = 0;

        for (&char, &lock) in iter {
            if lock == b'0' {
                free += 1; // Free to change
            } else if char == b'(' {
                balance += 1;
            } else {
                balance -= 1;
            }

            // Adjust balance using free parentheses
            if balance < 0 {
                if free == 0 {
                    return false;
                }
                balance += 1;
                free -= 1;
            }
        }

        balance <= free
    }
}

▲ 2 ▼ leetcoder 13-01-2025

Небезынтересно выглядит реализация этого же подхода на Go – у них весьма своеобразно реализуются итераторы в неожиданном для Go функциональном стиле. В реальной же практике такое редко гошники практикуют, как я понимаю, — гораздо проще байты строки in-place инвертировать.

// CharLockPair represents a character and its corresponding lock state.
type CharLockPair struct {
    char, lock rune
}

// Seq defines a functional iterator for yielding elements of type T.
type Seq[T any] func(func(T) bool)

// canBeValid checks if the given string can be a valid parentheses string.
func canBeValid(s, locked string) bool {
    if len(s)%2 != 0 {
        return false
    }

    // Forward pass
    if !checkBalance(forwardIter(s, locked)) {
        return false
    }

    // Backward pass
    if !checkBalance(backwardIter(s, locked)) {
        return false
    }

    return true
}

// checkBalance processes the iterator and determines if the sequence is balanced.
func checkBalance(seq Seq[CharLockPair]) bool {
    balance, free := 0, 0

    for pair := range seq {
        char, lock := pair.char, pair.lock

        if lock == '0' {
            free++
        } else if char == '(' {
            balance++
        } else {
            balance--
        }

        if balance < 0 {
            if free == 0 {
                return false // Stop iteration early
            }
            balance++
            free--
        }
    }

    return balance <= free
}

// forwardIter generates an iterator for the forward pass.
func forwardIter(s, locked string) Seq[CharLockPair] {
    return func(yield func(CharLockPair) bool) {
        for i := 0; i < len(s); i++ {
            if !yield(CharLockPair{char: rune(s[i]), lock: rune(locked[i])}) {
                return
            }
        }
    }
}

// backwardIter generates an iterator for the backward pass with swapped characters.
func backwardIter(s, locked string) Seq[CharLockPair] {
    return func(yield func(CharLockPair) bool) {
        for i := len(s) - 1; i >= 0; i-- {
            char := rune(s[i])
            if char == '(' {
                char = ')'
            } else {
                char = '('
            }
            if !yield(CharLockPair{char: char, lock: rune(locked[i])}) {
                return
            }
        }
    }
}
ответить