Programa Java para verificar se duas strings são anagramas | Programa de anagramas
Publicados: 2021-07-23Índice
Fatos menos conhecidos sobre Java
Sendo uma das linguagens de programação mais duráveis, o Java é usado em todo o mundo por causa de seus recursos robustos e flexíveis. A estabilidade e versatilidade do Java o tornaram uma das linguagens de programação mais procuradas. No entanto, existem vários fatos menos conhecidos sobre essa linguagem de programação segura. Vamos conhecer alguns deles.
- Oak é o nome original de Java.
- Você pode ganhar muito enquanto aprende esta linguagem de programação.
- Java é a segunda linguagem de programação mais populosa do mundo, sendo a primeira a C.
- Cerca de 3 bilhões de dispositivos em todo o mundo estão trabalhando em Java.
- Java é uma linguagem de programação sensível a maiúsculas e minúsculas. ou seja, “Final” e “final” não são a mesma coisa no código Java. Leia mais sobre por que o java é tão popular entre os desenvolvedores.
Uma visão geral do anagrama
Se uma string é transformada em outra string reorganizando seus caracteres, então as duas strings são chamadas de anagramas uma da outra. No entanto, o número de caracteres na string inicial e a string obtida devem ser os mesmos. Para entender melhor o conceito de anagrama, vamos considerar duas strings, 'deus' e 'cachorro'.
As strings 'god' e 'dog' são anagramas uma da outra porque a primeira string pode ser reorganizada para obter a última apenas trocando as posições dos caracteres 'd' e 'g'. Para quaisquer duas strings de entrada, a frequência de cada caractere é calculada para verificar se as strings são anagramas uma da outra ou não. Assim, um anagrama de uma string pode ser definido como qualquer outra string que tenha os mesmos caracteres com a mesma frequência da string de entrada em qualquer sequência.
Algoritmo para programa de anagramas em Java
Etapa 1: Defina as duas strings de entrada.
Passo 2: O comprimento de cada string é determinado. As strings de entrada não são anagramas umas das outras se tiverem comprimentos de string diferentes.
Etapa 3: Se as strings tiverem o mesmo comprimento, os caracteres da string serão convertidos em letras minúsculas para facilitar a comparação.
Etapa 4: Os caracteres de string são classificados por funções embutidas ou convertidos em uma matriz de caracteres e depois classificados.
Etapa 5: A matriz ordenada de caracteres é verificada quanto à igualdade.
Implementação do programa Anagram em Java
Existem várias soluções para implementar um código para descobrir se duas strings são anagramas ou não. Para cada solução discutida nas seções subsequentes, a Etapa 2 do algoritmo descrito acima forma a base e facilita a saída antecipada se os comprimentos das strings não corresponderem. Nas seções subsequentes, vamos entender mais sobre os diferentes tipos de escrita de um código para lógica de anagramas.
Abordagem de classificação
Os caracteres de cada string de entrada podem ser classificados para obter dois arrays de caracteres normalizados. Se as matrizes normalizadas de ambas as strings de entrada forem as mesmas, as strings serão consideradas anagramas uma da outra e vice-versa.
A compreensão e implementação deste código são mais fáceis. A complexidade de tempo da solução acima é O(n log n) e é necessário espaço adicional para armazenar matrizes de caracteres das strings de entrada.
Aprenda cursos de desenvolvimento de software online das melhores universidades do mundo. Ganhe Programas PG Executivos, Programas de Certificado Avançado ou Programas de Mestrado para acelerar sua carreira.
Abordagem de contagem para implementar a lógica de anagramas
Nesta abordagem, o número de existências de cada caractere nas duas strings de entrada é medido. Se a frequência de cada caractere em ambas as strings for idêntica, as strings serão anagramas uma da outra.
Vamos construir um único histograma para economizar memória. Na primeira string, as contagens de cada caractere são incrementadas, enquanto as contagens são decrementadas para a segunda. Se o resultado final equilibra tudo a zero, então as cordas são anagramas.
Esta solução executa mais rápido que a solução anterior e sua complexidade de tempo é O(n). No entanto, é necessário espaço adicional para contar os caracteres. Esta solução é praticamente eficaz apenas para strings com um intervalo de caracteres menor. Outro fato sobre esta solução é que ela usa um número limitado de funções Java incorporadas e, portanto, aumenta o comprimento do código.
Checkout: Ideias e tópicos do projeto Java
Determine anagramas verificando com o MultiSet
O uso do MultiSet, uma coleção que auxilia na comparação independente de ordem com elementos idênticos, simplifica o processo de contagem e comparação nesta solução.
Cada string de entrada é inicialmente convertida em um MultiSet de caracteres e, em seguida, verificada quanto à paridade.
A complexidade de tempo desta solução é O(n). É semelhante à abordagem de contagem para determinar anagramas. No entanto, pode funcionar eficientemente para strings de comprimentos maiores. Além disso, a codificação envolve um número maior de funções da Biblioteca Java.
Abordagem baseada em letras para determinar anagramas
Todas as soluções discutidas até agora consideram os caracteres de pontuação também como parte da string. Além disso, essas soluções diferenciam maiúsculas de minúsculas. A abordagem baseada em letras implementa um código para verificar as strings de entrada com base na definição linguística de anagramas. Nesta abordagem, os espaços em branco e as pontuações não são considerados como parte da string de entrada.
A etapa inicial ao implementar uma solução baseada em letras é a eliminação de caracteres indesejados e a conversão de todos os caracteres válidos em letras minúsculas. Após esta etapa, qualquer uma das implementações discutidas acima pode ser usada para verificar se as strings são anagramas ou não.
Se você estiver interessado em aprender mais sobre Java, desenvolvimento de software full-stack, confira o Executive PG Program in Software Development – Specialization in Full Stack Development do upGrad & IIIT-B, que é projetado para profissionais que trabalham e oferece mais de 500 horas de treinamento rigoroso , mais de 9 projetos e atribuições, status de ex-alunos do IIIT-B, projetos práticos práticos e assistência de trabalho com as principais empresas.
