Проверка скобочной последовательности с wildcard

Проверка скобочной последовательности с wildcard

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

Это усложненный вариант задачи о проверке скобок. Символ "*" (wildcard) может быть:

• Открывающей скобкой "("
• Закрывающей скобкой ")"
• Пустой строкой (удалён)

Нужно определить, существует ли хотя бы один способ замены "*" так, чтобы получилась валидная скобочная последовательность.

Подход 1: Динамическое программирование с интервалом

Используем DP, где отслеживаем диапазон возможных балансов:

def checkValidString(s: str) -> bool:
    # Минимум и максимум открытых скобок
    min_open = 0  # Минимальное количество открытых скобок
    max_open = 0  # Максимальное количество открытых скобок
    
    for char in s:
        if char == '(':
            min_open += 1
            max_open += 1
        elif char == ')':
            min_open -= 1
            max_open -= 1
        else:  # char == '*'
            min_open -= 1  # Если * заменим на )
            max_open += 1  # Если * заменим на (
        
        # Если max_open < 0 — невозможно исправить
        if max_open < 0:
            return False
        
        # min_open не может быть отрицательным
        # (слишком много закрывающих скобок)
        if min_open < 0:
            min_open = 0
    
    # В конце min_open должно быть 0 (все скобки закрыты)
    return min_open == 0

# Примеры
print(checkValidString("(*)"))    # True
print(checkValidString("(*))"))   # True
print(checkValidString(")(*"))    # False
print(checkValidString("(*)"))    # True
print(checkValidString("(*))"))   # True
print(checkValidString("\"*\""))    # True (пустая последовательность)
print(checkValidString("()"))     # True
print(checkValidString("(*(*)"))  # False

Логика:

1. Отслеживаем два счётчика:

   • min_open: минимальное количество открытых скобок (если * — это ")")
   • max_open: максимальное количество открытых скобок (если * — это "(")

2. Для каждого символа:

   • "(" увеличивает оба счётчика
   • ")" уменьшает оба счётчика
   • "*" может уменьшить min и увеличить max

3. Если max_open < 0: слишком много ")" — невозможно исправить

4. Если min_open < 0: устанавливаем в 0 (это лучший сценарий для уменьшения открытых скобок)

5. В конце min_open == 0 означает, что все скобки могут быть закрыты

Сложность:

• Временная: O(n) — один проход
• Пространственная: O(1) — только два числа

Подход 2: Двойной проход (Left-Right)

Сканируем слева направо и справа налево:

def checkValidString_v2(s: str) -> bool:
    n = len(s)
    
    # Слева направо: проверяем, что закрывающих больше открывающих
    open_count = 0
    for char in s:
        if char in '(*':
            open_count += 1
        else:  # char == ')'
            open_count -= 1
        
        # Если открытых скобок меньше, чем закрывающих
        if open_count < 0:
            return False
    
    # Справа налево: проверяем, что открывающих больше закрывающих
    close_count = 0
    for i in range(n - 1, -1, -1):
        char = s[i]
        if char in ')*':
            close_count += 1
        else:  # char == '('
            close_count -= 1
        
        if close_count < 0:
            return False
    
    return True

print(checkValidString_v2("(*)"))   # True
print(checkValidString_v2("(*))"))  # True
print(checkValidString_v2(")(*"))   # False

Подход 3: Рекурсия с мемоизацией

Для понимания логики задачи:

def checkValidString_recursive(s: str) -> bool:
    memo = {}
    
    def is_valid(index: int, open_count: int) -> bool:
        # Базовый случай: прошли всю строку
        if index == len(s):
            return open_count == 0
        
        # Проверяем мемоизацию
        if (index, open_count) in memo:
            return memo[(index, open_count)]
        
        # Если открытых скобок больше длины оставшейся части
        if open_count > len(s) - index:
            return False
        
        char = s[index]
        result = False
        
        if char == '(':
            result = is_valid(index + 1, open_count + 1)
        elif char == ')':
            if open_count > 0:
                result = is_valid(index + 1, open_count - 1)
        else:  # char == '*'
            # Вариант 1: * это (
            if is_valid(index + 1, open_count + 1):
                result = True
            # Вариант 2: * это )
            elif open_count > 0 and is_valid(index + 1, open_count - 1):
                result = True
            # Вариант 3: * это пусто
            elif is_valid(index + 1, open_count):
                result = True
        
        memo[(index, open_count)] = result
        return result
    
    return is_valid(0, 0)

print(checkValidString_recursive("(*)"))   # True
print(checkValidString_recursive("(*))"))  # True

Тестирование

import unittest

class TestCheckValidString(unittest.TestCase):
    def setUp(self):
        self.solution = checkValidString
    
    def test_basic(self):
        self.assertTrue(self.solution("(*)"))
        self.assertTrue(self.solution("(*))"))
        self.assertFalse(self.solution(")*("))
    
    def test_only_star(self):
        self.assertTrue(self.solution("*"))
        self.assertTrue(self.solution("**"))
        self.assertTrue(self.solution("***"))
    
    def test_only_brackets(self):
        self.assertTrue(self.solution("()"))
        self.assertFalse(self.solution(")"))
        self.assertFalse(self.solution("("))
    
    def test_complex(self):
        self.assertTrue(self.solution("(**))"))
        self.assertFalse(self.solution("(*)()"))
        self.assertTrue(self.solution("(())"))
    
    def test_edge_cases(self):
        self.assertTrue(self.solution(""))  # Пустая строка
        self.assertFalse(self.solution("))"))
        self.assertTrue(self.solution("(*()"))

Сравнение подходов

Ключевые моменты

1. Wildcard даёт три варианта замены — "(", ")" или пусто
2. min_open/max_open отслеживают диапазон возможных состояний
3. Если max_open < 0 — стопроцентно невалидно
4. Если min_open < 0 — сбрасываем в 0 (оптимистичный сценарий)
5. В конце min_open == 0 — гарантирует валидность

Практическое применение

Этот паттерн используется в:

• Парсерах с опциональными символами
• Регулярных выражениях с wildcards
• Проверке конфигураций
• Валидации языков программирования

Заключение

Это сложная, но элегантная задача. Ключ к решению — понять, что нужно отслеживать не одно значение (количество открытых скобок), а диапазон возможных значений, учитывая wildcard.