3 options for solving a popular problem

Formulation of the problem

Write a function that returns true if string s can be converted to string t by making no more than one of three changes: removing one character from s, adding one character to s, or replacing one character in 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) {
    }
  }

General simplifications

Removing a character from a string s is equivalent to adding a character to a string t. We go from 3 possible changes to 2 possible ones if we swap s and t so that s is always not shorter t:

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

1 solution option

Let's solve a simpler problem. Let's assume that the change is always made with the initial characters of the strings. Let's write an auxiliary function:

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

Let's count how many characters in the heads of the lines match. And apply the auxiliary function to the tails of the lines:

boolean check(String s, String t) {
  if(s.equals
  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));
}

Let's check the solution:

  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

Option 2 solution

You can do without substring. But the code will be more cumbersome:

boolean check(String s, String t) {
  if(s.equals
  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;
}

Option 3 solution

Let's move the code for counting matching characters in the heads of lines to an auxiliary function:

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

We will solve the problem by counting the lengths of common subsequences in the heads of the rows and in the tails.

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

boolean check(String s, String t) {
  if(s.equals
  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
  return i + j >= t.length() - 1;
}

Summary

All solutions work in linear time. I personally find the first solution more readable. But it is easy to make a mistake in the auxiliary function with substring – if the order of conditions in the logical OR is incorrect, there will be an array out of bounds error.

Thank you for reading my article. Subscribe to my channel: