3 варианта решения популярной задачи

Постановка задачи

Написать функцию, которая вернет true, если из строки s можно получить строку t, совершив не более, чем одно из 3х изменений: удаление одного символа из s, добавление одного символа в s, замена одного символа в s.

  class Solution {
    /*
    Вернуть true, если из строки s можно получить строку t,
    совершив не более, чем одно из 3х изменений]:
    - удалить из s один символ
    - добавить в s один символ
    - заменить в s один симв��л
    s = aaa t = aaa -> true
    s = baaa t = aaa -> true
    s = aaa t = aaab -> true
    s = aba t = aca -> true
    s = badca t = babba -> false
    s = badca t = badcaaa -> false
    */
    boolean check(String s, String t) {
    }
  }

Общие упрощения

Удаление символа из строки s эквивалентно добавлению символа в строку t. Перейдем от 3 возможных изменений к 2 возможным, если будем менять местами s и t, чтобы s всегда была не короче t:

boolean check(String s, String t) {
  if(s.equals(t)) return true;
  if(s.length() < t.length()) {
    String q = s; 
    s = t; 
    t = q;
  }
  if(s.length() - t.length() > 1) return false;
}

1 вариант решения

Решим более простую задачу. Предположим, что изменение всегда проводится с начальными символами строк. Напишем вспомогательную функцию:

boolean checkHelper(String s, String t) {
  return s.substring(1).equals(t) || s.substring(1).equals(t.substring(1));
}

Посчитаем, сколько символов в головах строк совпадают. И применим вспомогательную функцию к хвостам строк:

boolean check(String s, String t) {
  if(s.equals(t)) return true;
  if(s.length() < t.length()) {
    String q = s; 
    s = t; 
    t = q;
  }
  if(s.length() - t.length() > 1) return false;
  int i = 0;
  for(; i < t.length(); i++) {
    if(s.charAt(i) != t.charAt(i)) break;
  }
  return checkHelper(s.substring(i), t.substring(i));
}

Проверим решение:

Hidden text

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println("check true");
    System.out.println(s.check("aaa", "aaa"));
    System.out.println(s.check("baaa", "aaa"));
    System.out.println(s.check("aaa", "baaa"));
    System.out.println(s.check("caaa", "baaa"));
    System.out.println(s.check("aaa", "aaab"));
    System.out.println(s.check("aaab", "aaa"));
    System.out.println(s.check("aaab", "aaac"));
    System.out.println(s.check("aaba", "aaa"));
    System.out.println(s.check("aaa", "aaba"));
    System.out.println(s.check("aaba", "aaca"));
    System.out.println("check false");
    System.out.println(s.check("bcaaa", "aaa"));
    System.out.println(s.check("aaa", "bcaaa"));
    System.out.println(s.check("efaaa", "ghaaa"));
    System.out.println(s.check("aaa", "aaabc"));
    System.out.println(s.check("aaabc", "aaa"));
    System.out.println(s.check("aaaef", "aaagh"));
    System.out.println(s.check("aabca", "aaa"));
    System.out.println(s.check("aaa", "aabca"));
    System.out.println(s.check("aaefa", "aagha"));
  }

Вывод:

check true
true
true
true
true
true
true
true
true
true
true
check false
false
false
false
false
false
false
false
false
false

2 вариант решения

Можно обойтись без substring. Но код будет более громоздким:

boolean check(String s, String t) {
  if(s.equals(t)) return true;
  if(s.length() < t.length()) {
    String q = s; 
    s = t; 
    t = q;
  }
  if(s.length() - t.length() > 1) return false;
  int i = 0;
  for(; i < t.length(); i++) {
    if(s.charAt(i) != t.charAt(i)) break;
  }
  return checkHelper(s, t, i);
}

boolean checkHelper(String s, String t, int i) {
  int si = i + 1;
  int ti = (s.length() == t.length()) ? (i + 1) : i;
  for(; ti < t.length(); si++, ti++) {
    if(s.charAt(si) != t.charAt(ti)) 
      return false;
  }
  return true;
}

3 вариант решения

Вынесем во вспомогательную функцию код подсчета совпадающих символов в головах строк:

int checkHelper(String s, String t) {
  int i = 0;
  for(; i < t.length(); i++) {
    if(s.charAt(i) != t.charAt(i)) break;
  }
  return i;
}

Решим задачу через подсчет длин общих подпоследовательностей в головах строк и в хвостах.

String reverse(String s) {
  return new StringBuilder(s).reverse().toString();
}

boolean check(String s, String t) {
  if(s.equals(t)) return true;
  if(s.length() < t.length()) {
    String q = s; 
    s = t; 
    t = q;
  }
  if(s.length() - t.length() > 1) return false;
  int i = checkHelper(s, t);
  int j = checkHelper(reverse(s), reverse(t));
  return i + j >= t.length() - 1;
}

Итог

Все решения работают за линейное время. Первое решение лично мне видится более читаемым. Но в нем легко сделать ошибку во вспомогательной функции с substring - при неправильном порядке условий в логическом ИЛИ будет ошибка выхода за границы массива.

Спасибо, что прочитали мою статью. Подписывайтесь на мой канал:

Простой код

www.youtube.com