Если в Map ключом является закрывающая скобка, а значением — открывающая, это обычно связано с задачей проверки правильности скобочных последовательностей, где по закрывающей скобке быстро можно получить соответствующую открывающую.
Почему в Map ключом является закрывающая скобка, а значением открывающая? Что изменится если сделать наоборот? Какова сложность containsValue vs get по ключу?
Сложность операций:
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Если в Map ключом является закрывающая скобка, а значением — открывающая, это обычно связано с задачей проверки правильности скобочных последовательностей, где по закрывающей скобке быстро можно получить соответствующую открывающую.
Если поменять местами (ключ — открывающая, значение — закрывающая), логика проверки изменится: при обходе строки нужно будет искать закрывающую по открывающей, что тоже возможно, но обычно удобнее иметь закрывающую как ключ, чтобы при встрече закрывающей быстро проверить верхний элемент стека.
Сложность операций:
getпо ключу в Map — O(1) в среднем (хеш-таблица).containsValue— O(n), так как требует перебора всех значений.
Поэтому для проверки соответствия скобок лучше использовать get по ключу (закрывающей скобке), а не containsValue.