One Edit Away

Hay tres tipos de ediciones que se pueden realizar en un String: insertar un carácter, eliminar un carácter o reemplazar un carácter. Dadas dos Strings, escriba una función para verificar si están a una edición (o cero ediciones) de distancia. Por ejemplo:

EXAMPLE

pale, ple -> true 
pales, pale -> true 
pale, bale -> true 
pale, bake -> false 

👉 Link aquí hacia el repo para solucionar el problema

👌 Tips

Empieza con algo sencillo. Puedes chequear cada una de las condiciones que necesitas por separado?

Cuál es la relacion entre las opciones de insertar y remover caracteres? Crees que tienen que estar en chequeos separados?

Podrías hacer los tres chequeos de una sola vez?

👊 Solución 1

Para entender bien este problema es importante saber la diferencia que hay entre las 3 diferentes operaciones con las cuales podemos saber si las Strings están a 0 o 1 edición.

• Remplazar: Si cambiamos un caracter de “bale” - “pale” sabemos de que solamente son diferentes en un lugar.
• Insertar: Si insertamos un caracter de “aple” a “apple” sabemos de que están solamente a 1 carácter de diferencia.
• remover: lo mismo que el anterior - sí removemos un carácter de “apple” a “aple” sabemos que están a un carácter de diferencia.

Entonces podemos empezar a desarrollar funciones que nos van a ayudar para cada uno de estos escenarios:

boolean solution(String s1, String s2) {
  int s1Length = s1.length();
  int s2Length = s2.length();

  // should also perform checks to see if the strings lengths are in the valid “range”
  if (s1Length == s2Length) {
    return oneReplaceAway(s1, s2);
  } else if (s1Length > s2Length) {
    return oneInsertAway(s1, s2);
  } else if (s2Length > s1Length) {
    return oneInsertAway(s2, s1);
  }
  return false;
}

private boolean oneReplaceAway(String s1, String s2) {
  boolean difference = false;
  for (int I = 0; I < s1.length(); I++) {
      char c1 = s1.charAt(i);
      char c2 = s2.charAt(i);
      if (c1 != c2) {
        if ( difference) return false;
        difference = true;
      };

  }
  return true;
}

private boolean oneInsertAway(String s1, String s2) {
  ArrayList<Character> s1Chars = Utils.stringToCharArrayList(s1);
  ArrayList<Character> s2Chars = Utils.stringToCharArrayList(s2);
  boolean difference = false;

  for (int i = 0; i < s2.length(); i++) {
    char c1 = s1Chars.get(i);
    char c2 = s2Chars.get(i);

    if (c1 != c2) {
      if (difference) return false;
      s1Chars.remove(i);
      i--;
      difference = true;
    }
  }
  return true;
}

Si te das cuenta "oneInsertAway" puede ser utilizado también para “remover” ya que simplemente puedes invertir las Strings que están siendo pasadas a la función para saber si están a una inserción en vez de “oneRemovalAway”

---

Pregunta prestada del libro “Cracking the coding interview”