Pular para o conteúdo
Início » Série Preparação para Entrevistas: #8 – Validação de Parênteses

Série Preparação para Entrevistas: #8 – Validação de Parênteses

Introdução

Sejam bem-vindos ao oitavo artigo da nossa série “Preparação para Entrevistas“, uma jornada dos problemas mais comuns de programação que você pode encontrar em entrevistas técnicas. No artigo de hoje, vamos explorar o seguinte problema: o desafio dos Parênteses, Chaves e Colchetes Válidos. Embora eu, pessoalmente, nunca tenha enfrentado este problema específico em uma entrevista, sei de vários colegas que o encontraram e confirmam a sua relevância como um teste eficaz das habilidades de um programador em manipular estruturas de dados e algoritmos.

Este problema consiste em verificar se uma string composta apenas por parênteses '(' e ')', chaves '{' e '}' e colchetes '[' e ']' é válida. Isso significa que cada símbolo de abertura deve ser fechado por um símbolo correspondente na ordem correta. Por exemplo, "([]){}" é uma string válida, enquanto "([)]" não é.

Ao longo deste artigo, iremos não apenas definir o problema com exemplos ilustrativos, mas também ofereceremos uma solução em Java. Este exercício é uma oportunidade excelente tanto para a preparação de entrevistas quanto para o desenvolvimento do pensamento lógico e habilidades de codificação.

Explicação do Problema

No universo das entrevistas de técnicas, um problema comum é verificar a validade de uma sequência de parênteses, chaves e colchetes. A questão central é determinar se cada símbolo de abertura ('(', '{', '[') tem um correspondente de fechamento (')', '}', ']') na ordem correta. 

Veja alguns exemplos:

  1. Exemplo Válido:

    • String: "([]{})"
    • Análise: Cada símbolo de abertura encontra um par de fechamento na sequência correta. Primeiro, os parênteses, seguidos pelos colchetes, e por último, as chaves.

  2. Exemplo Inválido:

    • String: "{[}]"
    • Análise: Embora todos os tipos de símbolos sejam fechados, a ordem está incorreta. A chave de fechamento '}' vem antes do colchete de fechamento ']', quebrando a sequência válida.

  3. Outro Exemplo Inválido:

    • String: "((())"
    • Análise: Aqui, temos um parêntese de abertura sem o correspondente de fechamento, o que torna a string inválida.

Esses exemplos ilustram a importância de não apenas garantir que todos os símbolos de abertura tenham um par de fechamento, mas também que sigam a ordem correta. Na próxima seção, veremos um código em Java que resolve esse problema, identificando se uma string de símbolos é válida ou não.

Implementação em Java

Nossa abordagem para resolver o problema vamos utilizar uma combinação de pilha e mapa para gerenciar os caracteres. Aqui está o código:

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class ParentesesValidos {

    public static boolean isStringValida(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> caracteres = new HashMap<>();
        caracteres.put(')', '(');
        caracteres.put('}', '{');
        caracteres.put(']', '[');

        for (char caractere : s.toCharArray()) {
            if (caractere == '(' || caractere == '{' || caractere == '[') {
                stack.push(caractere);
            } else {
                Character abertura = caracteres.get(caractere);
                if (stack.isEmpty() || abertura != stack.pop()) {
                    return false;
                }
            }
        }
        return stack.empty();
    }

    public static void main(String[] args) {
        String chars = "([]{})";
        System.out.println(isStringValida(chars));
    }
}

Explicação do Código

  • Mapa de Caracteres: Utilizamos um mapa (HashMap) para associar cada símbolo de fechamento (')', '}', ']') ao seu correspondente de abertura ('(', '{', '[').
  • Pilha para Controle: A pilha armazena os símbolos de abertura. Quando encontramos um símbolo de fechamento, usamos o mapa para verificar se corresponde ao último símbolo de abertura na pilha.
  • Validação: Se a pilha estiver vazia (indicando que não há símbolo de abertura correspondente) ou se o símbolo de fechamento não corresponder ao esperado, a string é considerada inválida.
  • Verificação Final: Se a pilha estiver vazia no final da execução, isso significa que todos os símbolos foram adequadamente fechados e a string é válida.

Análise de Complexidade

Complexidade de Tempo

O algoritmo tem uma complexidade de tempo O(n), onde n é o número de caracteres na string de entrada. Isso ocorre porque percorremos a string uma vez, e cada operação que realizamos na pilha (push, pop) e no mapa (busca) é O(1), ou seja, leva um tempo constante.

Complexidade de Espaço

A complexidade de espaço do algoritmo também é O(n). O pior caso acontece quando todos os caracteres na string são símbolos de abertura, o que significa que todos eles seriam armazenados na pilha. Assim, no máximo, a pilha pode conter n elementos, onde n é o tamanho da string.

Conclusão

Chegamos ao final do nosso oitavo artigo da série “Preparação para Entrevistas“, onde abordamos o problema dos Parênteses Válidos, mas que também envolve Chaves e Colchetes Válidos. Este problema é um excelente exemplo de como conceitos simples de estruturas de dados podem ser aplicados para criar soluções elegantes e eficientes para questões complexas.

Através do código em Java, vimos como uma combinação de pilha e mapa pode ser utilizada para resolver esse problema de maneira eficaz. A análise de complexidade nos mostrou que nosso algoritmo é eficiente tanto em termos de tempo quanto de espaço, tornando-o uma solução adequada para esse tipo de desafio em entrevistas de emprego.

Espero que este artigo tenha tenha ajudado a fortalecer suas habilidades de programação e resolução de problemas. Fique atento para o próximo artigo da série, onde exploraremos outro tópico interessante e relevante para sua jornada de entrevistas de emprego.

Participe da Conversa

Se você achou este artigo útil ou tem suas próprias experiências e dicas sobre problemas de entrevistas de programação, adoraríamos ouvir de você! Compartilhe seus pensamentos nos comentários abaixo. Seu feedback não apenas ajuda a melhorar o conteúdo, mas também apoia outros leitores em sua jornada de aprendizado.

Além disso, se você está se preparando para entrevistas e achou este artigo útil, não esqueça de conferir os outros artigos da nossa série “Preparação para Entrevistas“. Cada artigo é projetado para fornecer insights valiosos e práticos em diferentes aspectos da programação e resolução de problemas.

Referências

Deixe um comentário