Это одна из самых простых задач по написанию кода, но вы все еще можете встретить ее на некотором предварительном техническом скрининге. Проблема выглядит так:
Учитывая строку, содержащую только символы
'(',')','{','}','['и']', определите, является ли входная строка допустимой.Скобки должны закрываться в правильном порядке,
"()"и"()[]{}"все действительны, но"(]"и"([)]"— нет.Описание взято из Leetcode (с) .
Как вы это решаете?
Мы использовали эту задачу для технологического скрининга. Что интересно, так это то, что многие люди на самом деле не знают, как с этим справиться (и заметьте, это категория «Easy» в Leetcode ). Некоторые люди пытаются использовать регулярные выражения; некоторые пытаются придумать решение грубой силы, проходящее через строку и считающее открывающие и закрывающие скобки. Если вы подумаете об этом, вы поймете, что ни того, ни другого не хватит. Например, как подсчет помогает в простейшем случае ([)] ?
Решение, которое должно прийти вам на ум, но, возможно, нет, если вы никогда не учились решать проблемы с кодированием, — это стек . Почему стек? Ну, потому что пара скобок или скобок может быть проверена только на полноту, когда вы видите закрывающую скобку; но это означает, что начальный должен быть где-то в ожидании и быть на вершине некоторой структуры данных для проверки. И структура, которая позволяет доступ LIFO, является стеком . Бывает, что у нас есть готовый класс Stack на Java .
Итак, как выглядит простое решение?
Основная идея заключается в том, что вы начинаете идти по струне. Если символ является одним из открывающих, вы помещаете его в стек. Если он закрывается, вы заглядываете в стек и смотрите, соответствует ли он. Если да, вы выталкиваете его из стека. Вы возвращаете true, если стек в конце пуст.
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
import java.util.*;public class Groups{ private static final List<Character> OPEN = Arrays.asList('(', '{', '['); private static final List<Character> CLOSE = Arrays.asList(')', '}', ']'); public static boolean groupCheck(String s){ if (s == null || s.length() == 0) { return true; } Stack<Character> stack = new Stack<>(); for (int i = 0; i < s.length(); i++) { char current = s.charAt(i); if (isOpen(current)) { stack.push(current); } else { if (stack.isEmpty()) { return false; } char prev = stack.peek(); if (isMatch(prev, current)) { stack.pop(); } } } return stack.isEmpty(); } private static boolean isOpen(char c) { return OPEN.contains(c); } private static boolean isClose(char c) { return CLOSE.contains(c); } private static boolean isMatch(char prev, char next) { return isOpen(prev) && (OPEN.indexOf(prev) == CLOSE.indexOf(next)); } } |
Есть ли другой способ решить эту проблему? Что если стек не придет вам в голову? Как всегда, есть несколько способов решить проблему. Давайте посмотрим на этот пример: ([]) {} .
Попробуем заменить правильно подобранные пары:
«([]) {}». Replace («[]», «») => «() {}». Replace («()», «») => «{}». Replace («{} ”,“ ”) =>“ ”
Таким образом, мы можем просто перебрать строку, заменив «{}», «()» и «[]» пустой строкой. Когда результат становится пустым, это означает, что все пары совпадают. Что если он не станет пустым; как мы вырвемся из цикла? Что ж, нам нужно проверить, изменилась ли длина строки после цикла замен. Если это не так, то мы сломаемся.
|
01
02
03
04
05
06
07
08
09
10
11
12
|
public class Groups{ public static boolean groupCheck(String s) { int len; do { len = s.length(); s = s.replace("()", ""); s = s.replace("{}", ""); s = s.replace("[]", ""); } while (len != s.length()); return s.length() == 0; }} |
Это выглядит даже лучше; просто и читабельно, но лучше ли это на самом деле? Я бы сказал, что нет, не совсем. Почему? Ну, потому что класс String является неизменным , и поэтому каждый раз, когда мы делаем это s.replace (), мы создаем новый строковый объект в куче.
Итак, как лучше это сделать? Можем ли мы переписать код, используя класс StringBuilder ? Ну, не напрямую, потому что у него нет метода replaceAll. Вы должны написать это самостоятельно, используя существующий метод замены . В библиотеке Apache Commons есть класс StrBuilder, у которого есть этот метод, но это не стандартный класс Java, вам нужно добавить зависимость.
Таким образом, даже эта простая задача может дать пищу для размышлений. Однако для собеседования подойдет любое из решений. Если стек не первая мысль в вашей голове, вы можете обойтись без.
| Ссылка: | Вопросы для интервью: проверьте скобки от нашей партнерши по JCG Марины Чернявской в блоге « Разработка программного обеспечения» и других животных . |