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”