Resolver problemas complexos usando recursão

Codificação otimizada

Recursão: Quando uma função chama a si mesma direta ou indiretamente, dividindo o problema em subconjuntos menores.

Basicamente, a recursão é uma pilha simples onde você empurra e abre seu método repetidamente para alcançar o resultado final.

Conforme mostrado abaixo, os métodos serão colocados em uma pilha até que a condição básica seja atingida. Depois que a condição básica é satisfeita, ele retrocede ou retira o método da pilha.

Este artigo é explicado supondo que você tenha conhecimento básico de codificação.

Vamos dar um exemplo do problema leetcode abaixo.

Dada uma string, particione sde forma que cada substring da partição seja um palíndromo. Retorne todo o particionamento palíndromo possível des .

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Codificar é quebrar problemas em pedaços e resolvê-los. Antes de analisar a técnica para decifrar o problema, vamos analisar e declarar as variáveis ​​necessárias. Antes de declarar, o que você deve ter em mente é declarar apenas as variáveis ​​necessárias com menos complexidade de espaço.

1. Encontre o tipo de dados das variáveis ​​necessárias

List<List<String>> result = new ArrayList<List<String>>();
List<String> strArray = new ArrayList<String>();

O motivo do problema é descobrir se as substrings são palíndromos. Quando uma palavra dá o mesmo significado, mesmo quando invertida, diz-se que é um palíndromo. Aqui precisamos encontrar todas as substrings possíveis para descobrir se são palíndromos ou não. Se a substring for palíndromo, iremos adicioná-la ao array, senão ela será ignorada.

3. Encontre as condições básicas

Para todos os problemas, deve haver condições básicas para interromper a recursão. Em nosso caso, podemos interromper o loop quando o iterador da string exceder o comprimento da string.

if(start>=s.length()){
    result.add(new ArrayList<String>(strArray));
}

A próxima tarefa é descobrir quando as condições devem ser repetidas. Quando uma substring é considerada um palíndromo, precisamos iniciar a recursão para verificar até mesmo os próximos caracteres das strings que formam um palíndromo. Se não for um palíndromo, podemos iterar a próxima string.

Para encontrar a substring, a string fornecida é quebrada e iterada para formar a matriz.

É claro que precisamos iterar a string fornecida uma a uma e também usar a recursão para encontrar todas as substrings.

Durante a primeira iteração da entrada dada, a string a é tomada, verifique se é palíndromo ou não. Se o palíndromo adiciona à lista e inicia a recursão ao longo da string até que a condição básica seja satisfeita. Quando a condição básica for satisfeita, adicione uma lista ao resultado e retroceda a linha para procurar outras substrings possíveis.

Da mesma forma, para a segunda e terceira iterações . Itere até a condição base para encontrar as possíveis substrings.

Com essa mesma lógica e modificando algum código, você pode resolver a maioria dos problemas de recursão.

import java.util.*;
class Solution {

  public List<List<String>> partition(String s) {
    List<List<String>> result = new ArrayList<List<String>>();
    List<String> strArray = new ArrayList<String>();
    backTrack(0, s, result, strArray);
    return result;
  }

  public void backTrack(int start, String s, List<List<String>> result,  List<String> strArray) {
    if (start >= s.length()) {
      result.add(new ArrayList<String>(strArray));
    }

    for (int itr = start; itr < s.length(); itr++) {
      if (isPalindrome(s, start, itr)) {
        strArray.add(s.substring(start, itr + 1));
        backTrack(itr + 1, s, result, strArray);
        strArray.remove(strArray.size() - 1);
        
      }
    }
  }

  public boolean isPalindrome(String str, int start, int end) {
    while (start < end) {
      if (str.charAt(start++) != str.charAt(end--)) return false;
    }
    return true;
  }
}

Comente sobre suas técnicas úteis de codificação.

Me encontre aqui:

www.linkedin.com/in/p-divya