Resolver problemas complejos usando recursividad

Codificación optimizada

Recursión: cuando una función se llama a sí misma directa o indirectamente al dividir el problema en subconjuntos más pequeños.

Básicamente, la recursividad es una pila simple en la que presiona y abre su método repetidamente para lograr el resultado final.

Como se muestra a continuación, los métodos se colocarán en una pila hasta que se alcance la condición base . Una vez que se cumple la condición base, retrocede o extrae el método de la pila.

Este artículo se explica asumiendo que tienes conocimientos básicos de codificación.

Tomemos un ejemplo del siguiente problema de leetcode.

Dada una cadena, particione stal que cada subcadena de la partición sea un palíndromo. Devuelve todas las posibles particiones palíndromo des .

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

La codificación se trata de dividir los problemas en partes y resolverlos. Antes de analizar la técnica para descifrar el problema, analizaremos y declararemos las variables necesarias. Antes de declarar, las cosas a tener en cuenta son declarar solo las variables requeridas con menos complejidad de espacio.

1. Encuentre el tipo de datos de las variables requeridas

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

El motivo del problema es encontrar si las subcadenas son palíndromos. Cuando una palabra da el mismo significado incluso cuando está invertida, se dice que es un palíndromo. Aquí necesitamos encontrar todas las subcadenas posibles para saber si es palíndromo o no. Si la subcadena es un palíndromo, la agregaremos a la matriz; de lo contrario, se omitirá.

3. Encuentra las condiciones base

Para todos los problemas, debe haber condiciones base para detener la recursividad. En nuestro caso, podemos romper el ciclo cuando el iterador de la cadena excede la longitud de la cadena.

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

La siguiente tarea es encontrar cuándo se van a repetir las condiciones. Cuando se descubre que una subcadena es un palíndromo, debemos iniciar la recursión para verificar que incluso los siguientes caracteres de las cadenas formen un palíndromo. Si no es un palíndromo, podemos iterar la siguiente cadena.

Para encontrar la subcadena, la cadena dada se rompe y se itera para formar la matriz.

Está claro que necesitamos iterar la cadena dada una por una y también usar la recursividad para encontrar todas las subcadenas.

Durante la primera iteración de la entrada dada, se toma la cadena a , compruebe si es palíndromo o no. If palindrome se suma a la lista y comienza la recursión a lo largo de la cadena hasta que se satisface la condición base. Cuando se cumpla la condición base, agregue una lista al resultado y retroceda en la fila para buscar otras subcadenas posibles.

Del mismo modo, para la segunda y tercera iteraciones . Iterar hasta la condición base para encontrar las posibles subcadenas.

Con esta misma lógica y modificando algún código, puedes resolver la mayoría de los problemas de recursión.

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 sus técnicas útiles de codificación.

Encuéntrame aquí:

www.linkedin.com/in/p-divya