Introdução
Neste artigo, vou apresentar a implementação de um desafio simples de validação de caracteres de texto em Java.
Se você não me conhece, meu nome é Henrique Otogami e seja bem-vindo(a) ao meu perfil no DevTo.
Comecei a utilizar a plataforma Leetcode para resolver outros desafios como esse. Esses desafios são utilizados em entrevistas, e na plataforma são separados por nível de dificuldade, por categorias, por listas de estudo e etc.
Desenvolvimento
01. Descrição
-- Certo, mas qual é o desafio?
O desafio consiste em analisar uma sequência de parênteses, colchetes e chaves, e verificar se a ordem de abertura e fechamento está correta.
Slide 01 - Quatro linhas de sequências de abertura e fechamento de parênteses
Slide 02 - Exemplos de sequências válidas (em verde) e inválidas (em vermelho) de parênteses
-- Parece simples, não é?
-- Na real, é simples mesmo.
A sequência deve ser informada em formato de texto, e deve conter apenas parênteses, colchetes e chaves. Outros caracteres não são permitidos.
Slide 03 - Descrição do desafio
No exemplo utilizado no slide 3, os caracteres são mostrados separadamente, mas foi feito dessa forma apenas para demonstrar os caracteres.
02. Requisitos
-- Agora, vamos aprofundar nas regras desse desafio.
-- Vem comigo.
Para realizar a validação da implementação da solução para esse problema, precisamos considerar os requisitos informados na descrição no Leetcode:
Os caracteres de abertura devem ser fechados por caracteres do mesmo tipo, porém de fechamento. Por exemplo, um parêntese deve ser aberto para ser fechado por outro parêntese. Ou, um parêntese não pode ser fechado por um colchete.
Os caracteres devem ser abertos para depois serem fechados. Embora pareça ser uma condição óbvia, é necessário explicitar todas as condições necessárias.
Todos os caracteres abertos devem ser fechados. Logo, o tamanho da sequência sempre é par e a quantidade de caracteres de abertura será igual a quantidade de caracteres de fechamento.
Slide 04- Requisitos de validação de sequências
03. Exemplos de validação
-- Tá, mas temos exemplos dessas regras de validação?
-- Temos.
Para exemplificar cada uma dessas condições de validação, separei em três exemplos:
Abertura e fechamento de um único par de parênteses:
Exemplo que representa apenas a condição mais simples possível.
Validação com retorno verdadeiro;Sequência de abertura e fechamento de parênteses, colchetes e chaves:
Exemplo que representa a condição de tipos diferentes, respeitando a ordem de abertura e fechamento corretamente.
Validação com retorno verdadeiro;Abertura de um tipo e fechamento de outro tipo:
Exemplo que representa a condição de ordem incorreta de abertura e fechamento.
Validação com retorno falso.
Slide 05 - Exemplos dos requisitos de validação de sequências
04. Considerações
-- E o código?
-- Já vamos chegar nessa etapa.
Antes disso, precisamos saber das duas restrições que foram impostas na descrição deste problema:
O tamanho da sequência deve ser maior que um e menor que dez mil caracteres;
A sequência deve conter apenas parênteses, colchetes e/ou chaves.
Durante a minha implementação, eu adicionei mais duas verificações:
Tamanho da sequência recebida deve ser par;
Tamanho da matriz de índices de fechamento deve ser zero no final do fluxo;
-- Não entendeu?
-- Maiores detalhes serão mostrados a seguir.
Slide 06 - Considerações de validação de sequências
05. Algoritmo
-- Ainda não é o código?
-- Não, mas esse é o algoritmo extraído do código implementado.
O algoritmo compõe a solução submetida e aceita no Leetcode, e será apresentado como uma visão panorâmica da implementação:
-- Iniciar o algoritmo recebendo a sequência de parênteses;
-- Verificar se o tamanho da sequência recebida é par;
-- Armazenar um caractere da sequência recebida;
-- Verificar se é um caractere de abertura:
---- É um caractere de abertura;
------ Armazenar o índice do caractere de fechamento;
------ Salvar o índice do caractere de fechamento na lista.
---- Não é um caractere de abertura;
------ Armazenar o último índice da lista;
------ Verificar se o caractere armazenado é igual ao último índice;
------ Remover o último índice da lista;
------ Definir que a sequência recebida é válida.
-- Verificar se terminou a sequência:
---- A sequência já terminou;
------ Verificar se o tamanho da lista é zero;
------ Retornar verdadeiro. A sequência recebida é válida;
------ Retornar falso. A sequência recebida é inválida.
---- A sequência não terminou;
------ Voltar a etapa 3.
Agora que sabemos as restrições, os requisitos, os exemplos e a visão panorâmica do algoritmo, vamos para a etapa de implementação dessa solução.
Slide 07 - Fluxograma do algoritmo para validação de parênteses
06. Implementação
A implementação desse algoritmo foi realizada utilizando o Java 8. Como desafio pessoal, tentei desenvolver da forma mais simples que eu consegui, pensando em deixar o código mais performático possível.
Slide 08 - Implementação do algoritmo de validação de parênteses
07. Conclusão
No momento de submissão desse código, a plataforma indica quanto tempo foi necessário para a execução e a quantidade de espaço utilizada. Nesta minha implementação, o tempo total foi de 13 milissegundos e 44MB de espaço.
Por fim, pretendo desenvolver mais desafios semelhantes a esse, para melhorar minhas competências técnicas, e trazê-los em forma de conteúdo.
LeetCode: implementação submetida
Ficou alguma dúvida ou tem sugestões?
Comente aqui embaixo ou me chame em alguma das minhas redes.
Valeu! ✌🏻
Muito obrigado!
Top comments (0)