content: package by.andd3dfx.string;
  
  import org.apache.commons.lang3.StringUtils;
  
  import static org.apache.commons.lang3.math.NumberUtils.min;
  
  /**
   * <pre>
   * Написать метод (класс и импорты не нужны) на вход которого приходит две строки.
   * На выходе надо проверить можно ли получить одну строку из другой за 1 исправление:
   * - замена одного символа в одной строке
   * - вставка/удаление одного символа из одной строки
   *
   * Примеры тестовых сценариев:
   * first = "a", second = "b" -> true
   * first = "ab", second = "b" -> true
   * first = "ab", second = "cb" -> true
   * first = "ab", second = "ba" -> false
   * first = "abcd", second = "abd" -> true
   * </pre>
   *
   * @see <a href="https://youtu.be/GOSWr4jHng8">Video solution</a>
   * @see <a href="https://youtu.be/0543ZryeIx4">Video solution 2</a>
   */
  public class StringTransformation {
  
      public static boolean couldTransform(String first, String second) {
          char[] s1 = first.toCharArray();
          char[] s2 = second.toCharArray();
  
          var len1 = s1.length;
          var len2 = s2.length;
  
          if (Math.abs(len1 - len2) > 1) {    // Lengths differ significantly
              return false;
          }
  
          if (len1 == len2) {                 // Same lengths
              var count = 0;
              for (var i = 0; i < len1; i++) {
                  if (s1[i] != s2[i]) {
                      count++;
                      if (count > 1) {
                          return false;
                      }
                  }
              }
              return true;
          }
  
          // Lengths differ by 1 - so need to remove/add one character
          var pos = 0;
          while (pos < len1 && pos < len2 && s1[pos] == s2[pos]) {
              pos++;
          }
  
          if (pos + 1 < len1 && pos < len2 && s1[pos + 1] == s2[pos]) {
              return remainingPartsShouldBeEqual(first, pos + 1, second, pos);
          }
          if (pos < len1 && pos + 1 < len2 && s1[pos] == s2[pos + 1]) {
              return remainingPartsShouldBeEqual(first, pos, second, pos + 1);
          }
  
          return true;
      }
  
      private static boolean remainingPartsShouldBeEqual(String first, int from1, String second, int from2) {
          return StringUtils.equals(
                  first.substring(from1),
                  second.substring(from2)
          );
      }
  
      public static boolean couldTransformUsingLevenshteinDistance(String first, String second) {
          return levenshteinDistance(first, second) <= 1;
      }
  
      /**
       * Use Wagner-Fisher algorithm. For details check
       * <a href="https://habr.com/ru/articles/676858/">article1</a>,
       * <a href="https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm">article2</a>
       *
       * @param str1 First string
       * @param str2 Second string
       * @return Levenshtein distance
       */
      public static int levenshteinDistance(String str1, String str2) {
          var m = str1.length();
          var n = str2.length();
          // for all i and j, d[i,j] will hold the distance between
          // the first i characters of s and the first j characters of t
          // note that d has (m+1)*(n+1) values
          var d = new int[m + 1][n + 1];
  
          // source prefixes can be transformed into empty string by
          // dropping all characters
          for (int i = 1; i <= m; i++) {
              d[i][0] = i;
          }
  
          // target prefixes can be reached from empty source prefix
          // by inserting every character
          for (int j = 1; j <= n; j++) {
              d[0][j] = j;
          }
  
          for (int j = 1; j <= n; j++) {
              for (int i = 1; i <= m; i++) {
                  var substitutionCost = (str1.charAt(i - 1) == str2.charAt(j - 1)) ? 0 : 1;
  
                  d[i][j] = min(d[i - 1][j] + 1,               // deletion
                          d[i][j - 1] + 1,                        // insertion
                          d[i - 1][j - 1] + substitutionCost);    // substitution
              }
          }
          return d[m][n];
      }
  }
  