Leetcode #1: verificando parênteses válidos

Na faculdade o que me fez temer a área da programação foi a disciplina de algoritmos e estrutura de dados. Nesta disciplina eu precisei aprender a implementar várias estruturas de dados como pilhas, listas encadeadas e árvores binárias.

Foi depois desta disciplina que resolvi que não queria fazer engenharia da computação e fui cursar engenharia mecânica. E olha só, o destino quis que eu voltasse a me encontrar com a programação e aquilo que era um trauma para mim, decidi transformar em um ponto forte.

É por isso que sempre que posso dedico um tempinho (as vezes um tempão rsrs) para resolver desafios de código no Leetcode. E como trabalho a um tempo com JavaScript, resolvi usar esta linguagem para resolver os desafios começando pelos fáceis, que muitas vezes não parecem fáceis rsrs.

E para que a solução não fique apenas lá na plataforma, resolvi compartilhar ela aqui neste artigo e aproveitar para explicar em como pensei e quais soluções usei, inclusive recursos úteis do JavaScript moderno que pouca gente normalmente usa.

Vem comigo!

O desafio

O desafio da vez era implementar uma função que:

Dada uma string ”s” contendo apenas os caracteres '(', ')', '{', '}', '[' e ']', determine se a string de entrada é válida.

Uma string de entrada é válida se:

1. Os colchetes/parênteses/chaves abertos devem ser fechados pelo mesmo tipo de colchetes.

2. Os colchetes/parênteses/chaves abertos devem ser fechados na ordem correta.

3. Cada suporte próximo tem um suporte aberto correspondente do mesmo tipo.

Exemplo 1:

• Entrada: s = "()"

• Saída: verdadeiro

Exemplo 2:

• Entrada: s = "()[]{}"

• Saída: verdadeiro

Exemplo 3:

• Entrada: s = "(]"

• Saída: falso

Exemplo 4:

• Entrada: s = "([])"

• Saída: verdadeiro

Antes de mostrar a minha solução, vai pensando aí em como você resolveria isso e depois continua a leitura, beleza?

Minha solução

A primeira coisa que veio na minha cabeça foi percorrer o array e quando encontrar um parênteses que abre ‘’(’’ ( e aqui eu uso o parênteses mas poderia ser uma chave ou colchetes) guardar ele em um array. Logo depois eu iria procurar por um parênteses que fecha e verificar se ele vem logo depois do de abertura. Na minha cabeça eu iria fazer isso no array e se funcionasse eu teria a solução.

Então, normalmente assim de cara a primeira coisa que você pensa não será a melhor solução, mas provavelmente estará no caminho dela. A menos que você tenha uma prática muito afiada em resolver problemas de código e já tiver resolvidos muitos mesmo é que você olhará para o problema e terá uma ideia mais clara da solução.

Isso aconteceu comigo e apesar da minha ideia inicial fazer sentido iria ser complicado ficar colocando vários ifs dentro de um for e salvar isso em um novo array. Mas o caminho é por aí. Foi então que aproveitando as dicas da plataforma eu consegui ter uma ideia melhor e minha solução final ficou assim:

var isValid = function (s) {
  let stack = [];
  bracketsMap = { ")": "(", "]": "[", "}": "{" };

  for (const bracket of s) {
    if (bracket in bracketsMap) {
      if (stack.length && stack[stack.length - 1] === bracketsMap[bracket]) {
        stack.pop();
      } else {
        return false;
      }
    } else {
      stack.push(bracket);
    }
  }
  return stack.length === 0;
};

Agora vamos esmiuçar essa solução e entender o que ela faz, além de aprender algumas coisinhas legais do JavaScript e de estrutura de dados. Vamos lá!

Destrinchando o código

Sempre que encontramos um caractere de abertura (”(”, “{”, “[”), vamos guardar ele numa pilha. Quando vier um caractere de fechamento (”)”, “}”, “]”), verificamos se ele fecha o último que colocamos na pilha (”stack”).

A pilha é perfeita pra isso porque é LIFO (último a entrar, primeiro a sair). Ou seja, o último caractere aberto é o primeiro que precisa ser fechado. Se isso não acontecer, a string já está errada.

Também criamos um objeto JavaScript (”bracketsMap”). Ele associa cada caractere de fechamento ao seu correspondente caractere de abertura. Agora vamos pro loop!

O “for...of” percorre cada caractere da string “s”, como '(', '{', '[', etc. Em cada iteração, o código verifica se o caractere atual é um fechamento (como “)”, “]”, “}”) usando o operador “in”, que checa se ele existe como chave no objeto “bracketsMap”. Se for, ele compara com o topo da pilha (”stack[stack.length - 1]”) para ver se é o par correto. Se bater, remove o último item da pilha com “pop()”; caso contrário, a função retorna false imediatamente.

Se o caractere não for um fechamento, então é uma abertura e é simplesmente empilhado. A pilha serve para guardar os caracteres que ainda estão "em aberto", esperando seus pares de fechamento. Esse processo se repete até o final da string, validando cada par na ordem.

No fim, a função retorna “true” apenas se a pilha estiver vazia, o que indica que todos os pares foram fechados corretamente. Se restar algo na pilha, significa que houve uma abertura sem fechamento correspondente, e o resultado será “false”.

Considerações

Bom, a ideia da pilha veio da dica da plataforma. Minha ideia inicial apesar de ter um pouco de sentido provavelmente iria em resultar em mais código, mais complexidade e legibilidade, muito provavelmente rsrs. E foram várias tentativas até chegar na solução que achei mais interessante.

E o legal do Leetcode é que você pode visualizar as soluções de outras pessoas, além de um “score” que indica o quão performático a sua solução é em relação às outras soluções para o mesmo problema. Isso é bem legal, pois além de mostrar o quão bom e performático está seu código, a plataforma ainda te incentiva a melhorá-lo. Achei isso bem interessante!

Este foi um desafio considerado fácil na plataforma, mas sendo sincero eu achei complexo um pouco. Até quem conhece o conceito de pilha mas não usa normalmente no dia a dia como dev vai ter talvez um pouco de dificuldades, e foi o meu caso.

Espero que este artigo tenha te ajudado ou te motivado a estudar mais essa parte mais técnica na programação.

Grande abraço e até a próxima!