Kodr

Kodr

  • Contenido
  • Blog
  • About
  • Languages iconEspañol
    • English

›Problems: Arrays & Strings

Technical Interviews

  • What are technical interviews based on?
  • Contenido esencial y cómo resolver algoritmos

Notación Big-O

  • Notación Big-O
  • Ejemplos Big-O
  • Ejercicios Big-O

Optimisation Techniques

  • Optimización BUD
  • DIY Optimisation

Key Concepts

  • Linked Lists
  • Stack & Queues
  • Trees
  • Graphs
  • Tries
  • Sorting
  • Searching
  • Recursion
  • Dynamic Programming

Problems: Arrays & Strings

  • Is Unique
  • String Rotation
  • Check Permutacion
  • URLify
  • One Edit Away
  • String Compression
  • Rotate Matrix
  • Zero Matrix
  • Valid Parenthesis

Problems: Linked Lists

  • Remove duplicates
  • Kth to last node
  • Delete Middle Node
  • Partition
  • Sum List
  • Palindrome
  • Intersection
  • Loop Detection

Problems: Stacks & Queues

  • Stack Min
  • Stack Of Plates
  • Queue via Stacks
  • Sort Stack
  • Animal Shelter

Problems: Trees

  • Path Sum
  • Construct Binary Tree from Inorder and Postorder Traversal

Problems: Binary Search Trees & Graphs

  • Route Between Two Nodes
  • Minimal Tree
  • List of Depths
  • Check Balanced
  • Validate BST
  • Successor
  • Build Order
  • First Common Ancestor
  • Check Sub-Tree
  • (Harder) Random Node

Problems: Sorting & Searching

  • Merge Sorted Array
  • First Bad Version

Problems: Dynamic Programming

  • Triple Step
  • Magic Index
  • (Hard) Towers Of Hanoi

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

imagen

👌 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”

Last updated on 3/1/2020
← URLifySiguiente →
  • 👉 Link aquí hacia el repo para solucionar el problema
  • 👌 Tips
  • 👊 Solución 1
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright © 2021 Kodr