161. One Edit Distance

leetcode medium

#csharp#leetcode#medium#string#tree

Task

Даны две строки s и t. Верните true, если они отличаются ровно на одну операцию редактирования, иначе верните false.

Строка s считается отличающейся на одну операцию редактирования от строки t, если можно:

- Вставить ровно один символ в строку s, чтобы получить t.

- Удалить ровно один символ из строки s, чтобы получить t.

- Заменить ровно один символ в строке s на другой символ, чтобы получить t.

Пример:

Input: s = "ab", t = "acb"

Output: true

Explanation: We can insert 'c' into s to get t.

C# solution

matched/original

public class Solution {
    public bool IsOneEditDistance(string s, string t) {
        int ns = s.Length;
        int nt = t.Length;
        if (ns > nt)
            return IsOneEditDistance(t, s);
        if (nt - ns > 1)
            return false;
        for (int i = 0; i < ns; i++)
            if (s[i] != t[i])
                if (ns == nt)
                    return s.Substring(i + 1) == t.Substring(i + 1);
                else
                    return s.Substring(i) == t.Substring(i + 1);
        return ns + 1 == nt;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool IsOneEditDistance(string s, string t) {
        int ns = s.size();
        int nt = t.size();
        if (ns > nt)
            return IsOneEditDistance(t, s);
        if (nt - ns > 1)
            return false;
        for (int i = 0; i < ns; i++)
            if (s[i] != t[i])
                if (ns == nt)
                    return s.Substring(i + 1) == t.Substring(i + 1);
                else
                    return s.Substring(i) == t.Substring(i + 1);
        return ns + 1 == nt;
    }
}

Java solution

matched/original

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int ns = s.length();
        int nt = t.length();
        if (ns > nt) return isOneEditDistance(t, s);

        if (nt - ns > 1) return false;

        for (int i = 0; i < ns; i++) {
            if (s.charAt(i) != t.charAt(i)) {
                if (ns == nt) {
                    return s.substring(i + 1).equals(t.substring(i + 1));
                } else {
                    return s.substring(i).equals(t.substring(i + 1));
                }
            }
        }
        return (ns + 1 == nt);
    }
}

JavaScript solution

matched/original

var isOneEditDistance = function (s, t) {
    let ns = s.length;
    let nt = t.length;
    if (ns > nt) return isOneEditDistance(t, s);
    if (nt - ns > 1) return false;

    for (let i = 0; i < ns; i++)
        if (s[i] != t[i])
            if (ns == nt)
                return s.slice(i + 1) === t.slice(i + 1);
            else return s.slice(i) === t.slice(i + 1);
    return ns + 1 === nt;
};

Python solution

matched/original

class Solution:
    def isOneEditDistance(self, s: "str", t: "str") -> "bool":
        ns, nt = len(s), len(t)
        if ns > nt:
            return self.isOneEditDistance(t, s)
        if nt - ns > 1:
            return False

        for i in range(ns):
            if s[i] != t[i]:
                if ns == nt:
                    return s[i + 1 :] == t[i + 1 :]
                else:
                    return s[i:] == t[i + 1 :]
        return ns + 1 == nt

Go solution

matched/original

func isOneEditDistance(s string, t string) bool {
    ns := len(s)
    nt := len(t)
    if ns > nt {
        return isOneEditDistance(t, s)
    }
    if nt-ns > 1 {
        return false
    }

    for i := 0; i < ns; i++ {
        if s[i] != t[i] {
            if ns == nt {
                return s[i+1:] == t[i+1:]
            } else { // If strings have different lengths
                return s[i:] == t[i+1:]
            }
        }
    }
    return ns+1 == nt
}

Explanation

Algorithm

1️⃣

Проверка длины строк:

Убедитесь, что строка s короче строки t. Если это не так, поменяйте их местами и повторите проверку.

Если разница в длине между s и t больше 1, то строки невозможно привести к равенству одной операцией редактирования, верните false.

2️⃣

Сравнение строк посимвольно:

Проходите по строке s и сравнивайте каждый символ с соответствующим символом в строке t.

Если находите различающийся символ:

Если длины строк равны (ns == nt), проверьте, равны ли подстроки после текущего символа для обеих строк (s.substr(i + 1) == t.substr(i + 1)). Если равны, возвращайте true, иначе false.

Если длины строк различаются, проверьте, равна ли подстрока s начиная с текущего символа подстроке t начиная с следующего символа (s.substr(i) == t.substr(i + 1)). Если равны, возвращайте true, иначе false

3️⃣

Проверка на возможное добавление символа в конец s:

Если после посимвольного сравнения не было найдено различий на всей длине s и t длиннее s на один символ, это означает, что t можно получить добавлением одного символа в конец s. В этом случае верните true.

В противном случае верните false, так как это означает, что t либо имеет больше отличий, либо такой же размер как s без возможности привести их к равенству одной операцией редактирования.

😎