String reversa em Java: aprendendo a reverter strings de maneiras diferentes

É possível se tornar um bom programador sem conhecer algoritmos? Muito, muito controverso. Sim, você pode encontrar emprego em nossas empresas de terceirização, pois durante as entrevistas eles fazem perguntas principalmente sobre tecnologia. Mas você será um bom especialista se suas decisões estiverem cheias de muletas? Se você quiser mudar para uma empresa estrangeira mais séria, encontrará entrevistas focadas principalmente em algoritmos. De uma forma ou de outra, vale a pena adotar os algoritmos mais básicos, pois algoritmo é amigo do programador . Hoje abordaremos um desses tópicos e discutiremos maneiras de reverter uma string. Tudo é simples aqui. Inverter uma string é retroceder a string. Por exemplo: JavaRush para sempre ->reverof hsuRavaJ Então, como você pode reverter uma string em Java?

1.StringBuilder/StringBuffer

A maneira mais comum e simples é usar StringBuilder/StringBuffer :

public static String reverseString(String str) {
  return new StringBuilder(str).reverse().toString();
}

Melhor solução = mais simples. Quando questionado sobre como reverter uma string em Java, esta é a primeira coisa que deve vir à mente. Mas já falamos sobre algoritmos, não é? Vamos dar uma olhada em soluções que não estão prontas para uso.

2. Solução de matriz

public static String reverseString(String str) {
  char[] array = str.toCharArray();
  String result = "";
  for (int i = array.length - 1; i >= 0; i--) {
     result = result + array[i];
  }
  return result;
}

Convertemos nossa string em um array usando o método toCharArray . Vamos executar um loop for por esse array desde o final, adicionando caracteres à string resultante ao longo do caminho.

3. Solução com charAt

public static String reverseString(String str) {
  String result = "";
  for (int i = 0; i < str.length(); i++) {
     result = str.charAt(i) + result;
  }
  return result;
}

Nesse caso, nem precisamos dividir a string em um array, pois extraímos cada caractere usando o método da classe String - charAt (o loop for, novamente, é reverso, o que nos permite levar os caracteres sequencialmente para trás).

4. Solução com pilha

A classe Stack não é usada há muito tempo e é considerada obsoleta, mas mesmo assim, para referência, será útil ver uma solução que a utiliza:

public static String reverseString(String str) {
  Stack<Character> stack = new Stack<>();
  String result = "";
  for (Character character : str.toCharArray()) {
     stack.add(character);
  }
  while (!stack.isEmpty()) {
     result = result + stack.pop();
  }
  return result;
}

Aqui novamente usamos toCharArray para dividir a string em um array e colocar tudo em nossa Stack com um tipo genérico Character . A seguir, começamos a retirar os elementos do topo da pilha. Devido à natureza da pilha como uma estrutura LIFO - L ast I n F irst Out (primeiro a entrar, último a sair), os elementos serão levados para trás e o resultado será armazenado na linha resultante.

5. Solução por recursão

Quase todos os problemas de algoritmo podem ser resolvidos usando recursão. E aqui também não podemos viver sem ela. Ou mesmo sem eles. Afinal, hoje consideraremos não apenas um método para resolver a recursão, mas vários.

• método um

  public static String reverseString(String str) {
    String rightStr;
    String leftStr;
    int length = str.length();
  
    if (length <= 1) {
       return str;
    }
  
    leftStr = str.substring(0, length / 2);
    rightStr = str.substring(length / 2, length);
  
    return reverseString(rightStr) + reverseString(leftStr);
  }

  Usamos as variáveis ​​rightStr e leftStr para dividir a string recebida em duas partes iguais. A seguir, usando esta divisão, dividimos a string nas menores partes divisíveis (1 caractere). Depois a recursão começa a entrar em colapso, retornando os caracteres na ordem inversa (os que estavam à direita foram colocados à esquerda; os que estavam à esquerda foram colocados à direita)

  Não devemos esquecer que cada recursão é uma chamada múltipla a um método e, como resultado, um gasto considerável de recursos. Bem, se estamos falando de recursão com uma condição de saída inatingível, então este é o caminho para o infinito e para StackOverflowError.

• método dois

  Aqui precisamos de um argumento adicional no método - index.

  Quando este método é executado, ele recebe um comprimento de string de -1:

  String str = "JavaRush forever";
  System.out.println(reverseString(str, str.length()-1));

  E o método em si:

  public static String reverseString(String str, int index) {
    if(index == 0){
       return str.charAt(0) + "";
    }
  
    char letter = str.charAt(index);
    return letter + reverseString(str, index-1);
  }

  Nosso índice serve como um indicador de qual elemento da linha usaremos agora (e usaremos os elementos do final).

  Portanto, definimos condições de saída quando o índice atinge o primeiro elemento.

Somamos os valores obtidos através do índice de letras com o resultado da execução anterior do método e retornamos o resultado.

• método três

  public static String reverseString(String str) {
    if (str.length() <= 1) {
       return str;
    }
    return reverseString(str.substring(1)) + str.charAt(0);
  }

  Este método é essencialmente o mais simples dos recursivos. E como lembramos, simples = melhor.

  Durante cada execução, especificamos a mesma string, mas sem o primeiro elemento. Quando a condição de saída é alcançada (quando temos um caractere restante), a recursão começa a entrar em colapso e o caractere anterior não utilizado será adicionado a cada resultado subsequente.

6. Usando XOR

XOR é uma operação lógica bit a bit. No caso de duas variáveis, o resultado de uma operação é verdadeiro se e somente se um dos argumentos for verdadeiro e o outro for falso. Você pode ler mais sobre operações bit a bit neste artigo . A próxima solução dependerá do fato de que:

(A XOR B) XOR B = A
(A XOR B) XOR A = B

Como será o método:

public static String reverseString(String str) {
  char[] arr = str.toCharArray();
  int low = 0;
  int high = arr.length - 1;
  String result = "";
  while (low < high) {
     arr[low] = (char) (arr[low] ^ arr[high]);
     arr[high] = (char) (arr[low] ^ arr[high]);
     arr[low] = (char) (arr[low] ^ arr[high]);
     low++;
     high--;
  }
  for (int i = 0; i < arr.length; i++) {
     result = result + arr[i];
  }
  return result;
}

Vamos descobrir o que está acontecendo aqui. Criamos um array a partir da string recebida. Criamos duas variáveis, low e high , que armazenam índices para percorrer o array. Conseqüentemente, um se moverá do começo ao fim - damos a ele o valor 0, o segundo - do fim ao começo, definimos arr.length - 1 . Entramos em um loop que será reproduzido enquanto o índice alto for maior que baixo . É aqui que a diversão começa a acontecer – o uso de sala cirúrgica exclusiva. Vejamos x e y como exemplo . Suponha que arr[high] = 'x'; Seu código binário será 1 1 1 1 0 0 0 Neste momento arr[high] = 'n'; Código binário - 1 1 0 1 1 1 0 O que teremos nas operações XOR em loop:

1. arr[baixo] = (char) (arr[baixo] ^ arr[alto]);

   
   arr[low] = 1 1 0 1 1 1 0
   arr[high] =1 1 1 1 0 0 0
   arr[low] = 0 0 1 0 1 1 0

2. arr[alto] = (char) (arr[baixo] ^ arr[alto]);

   
   arr[low] =  0 0 1 0 1 1 0
   arr[high] = 1 1 1 1 0 0 0
   arr[high] = 1 1 0 1 1 1 0

3. arr[baixo] = (char) (arr[baixo] ^ arr[alto]);

   
   arr[low] =  0 0 1 0 1 1 0
   arr[high] = 1 1 0 1 1 1 0
   arr[low] =  1 1 1 1 0 0 0

Como resultado, graças a essas operações, trocamos os valores de duas células do array. arr[high] tem tantos elementos do final do array quanto arr[low] tem do início. Portanto, simplesmente trocamos os elementos por esses índices. Por exemplo, na primeira execução da frase “JavaRush para sempre” J e r serão trocados, na segunda - a e e , etc. meio, seremos expulsos do loop (ou seja, não há necessidade de alterar o elemento do meio). Se for par, seremos expulsos após processar todos os elementos. Bem, depois disso entramos em um loop regular e construímos uma string a partir dos elementos do array.