Различаются ли строки не более чем на один символ?
1,00
р.
Есть две строки как проверить, что из одной можно сделать другую при помощи вставки, удаления или замены не более чем одного символа?
Ответ
Минимальное количество операций вставки, удаления и замены символа, необходимое для преобразования одной строки в другую, называется расстоянием Левенштейна. В общем случае оно вычисляется за O(n*m), где n и m - длины строк.
Однако, в данном случае требуется не вычислить количество действий, а проверить, возможно ли сделать преобразование за 0 (строки изначально одинаковые) или 1 действие.
Рассмотрим две строки. Выделим наидлиннейший одинаковый префикс и наидлиннейший одинаковый суффикс (допускается, что один или оба найденных куска могут быть пустыми). Очевидно, что в этих кусках нам ничего менять не требуется. Центральной частью строки назовём участок между префиксом и суффиксом.
Рассмотрим несколько возможных ситуаций:
(1) Префикс и суффикс совпадают со всей строкой. Строки были изначально одинаковы. Конкатенация префикс и суффикса даёт одну из строк. В таком случае для того, чтобы преобразование было возможно, необходимо и достаточно, чтобы центральная часть другой строки состояла из одного символа. Понадобится операция вставки или удаления. Центральная часть обеих строк состоит из одного символа. Нужна операция замены. Центральная часть хотя бы одной из строк состоит из нескольких символов. Преобразование невозможно. (2) Т. о. для различных строк необходимо и достаточно, чтобы центральная часть каждой из строк была не длиннее одного символа.
Несколько преобразуем этот алгоритм:
Найдём индекс S, указывающий на следующий символ за одинаковым префиксом (возможно, длина строки плюс 1). Найдём индексы E1 и E2, указывающие на символ, предшествующий одинаковому суффиксу в первой и второй строках соответственно (возможно, -1). Они могут различаться, т. к. длина строк может быть разной. В случае 1 получим S=Length+1, E1=-1, E2=-1. Центральная часть нулевой длины означает, что указатель конца будет стоять раньше указателя начала на 1 символ. Центральная часть из одного символа будет представлена равными указателями конца и начала. Во всех остальных случаях указатель конца будет больше. Т. о. для (2) условие превратится в такое: Для обеих строк указатель конца не превосходит указателя начала. Заметим, что для одинаковых строк это условие так же выполняется. Если язык позволяет, то можно (в качестве дополнительной оптимизации) сначала проверить, что длины строк отличаются не более чем на 1.
А теперь в коде:
Public Function AreSimilar(ByVal Str1 As String, ByVal Str2 As String) As Boolean If Math.Abs(Str1.Length - Str2.Length) > 1 Then Return False
Dim S As Integer = 0 Dim E1 As Integer = Str1.Length - 1, E2 As Integer = Str2.Length - 1 Dim MinLength As Integer = Math.Min(E1 + 1, E2 + 1)
Do While S < MinLength AndAlso Str1(S) = Str2(S) S += 1 Loop
Do While Not E1 AndAlso Not E2 AndAlso Str1(E1) = Str2(E2) E1 -= 1 E2 -= 1 Loop
Return E1 <= S And E2 <= S End Function <br>Асимптотика линейная. В худшем случае (при одинаковых строках) делается по два полных прохода по каждой из строк.
Ответ
Минимальное количество операций вставки, удаления и замены символа, необходимое для преобразования одной строки в другую, называется расстоянием Левенштейна. В общем случае оно вычисляется за O(n*m), где n и m - длины строк.
Однако, в данном случае требуется не вычислить количество действий, а проверить, возможно ли сделать преобразование за 0 (строки изначально одинаковые) или 1 действие.
Рассмотрим две строки. Выделим наидлиннейший одинаковый префикс и наидлиннейший одинаковый суффикс (допускается, что один или оба найденных куска могут быть пустыми). Очевидно, что в этих кусках нам ничего менять не требуется. Центральной частью строки назовём участок между префиксом и суффиксом.
Рассмотрим несколько возможных ситуаций:
(1) Префикс и суффикс совпадают со всей строкой. Строки были изначально одинаковы. Конкатенация префикс и суффикса даёт одну из строк. В таком случае для того, чтобы преобразование было возможно, необходимо и достаточно, чтобы центральная часть другой строки состояла из одного символа. Понадобится операция вставки или удаления. Центральная часть обеих строк состоит из одного символа. Нужна операция замены. Центральная часть хотя бы одной из строк состоит из нескольких символов. Преобразование невозможно. (2) Т. о. для различных строк необходимо и достаточно, чтобы центральная часть каждой из строк была не длиннее одного символа.
Несколько преобразуем этот алгоритм:
Найдём индекс S, указывающий на следующий символ за одинаковым префиксом (возможно, длина строки плюс 1). Найдём индексы E1 и E2, указывающие на символ, предшествующий одинаковому суффиксу в первой и второй строках соответственно (возможно, -1). Они могут различаться, т. к. длина строк может быть разной. В случае 1 получим S=Length+1, E1=-1, E2=-1. Центральная часть нулевой длины означает, что указатель конца будет стоять раньше указателя начала на 1 символ. Центральная часть из одного символа будет представлена равными указателями конца и начала. Во всех остальных случаях указатель конца будет больше. Т. о. для (2) условие превратится в такое: Для обеих строк указатель конца не превосходит указателя начала. Заметим, что для одинаковых строк это условие так же выполняется. Если язык позволяет, то можно (в качестве дополнительной оптимизации) сначала проверить, что длины строк отличаются не более чем на 1.
А теперь в коде:
Public Function AreSimilar(ByVal Str1 As String, ByVal Str2 As String) As Boolean If Math.Abs(Str1.Length - Str2.Length) > 1 Then Return False
Dim S As Integer = 0 Dim E1 As Integer = Str1.Length - 1, E2 As Integer = Str2.Length - 1 Dim MinLength As Integer = Math.Min(E1 + 1, E2 + 1)
Do While S < MinLength AndAlso Str1(S) = Str2(S) S += 1 Loop
Do While Not E1 AndAlso Not E2 AndAlso Str1(E1) = Str2(E2) E1 -= 1 E2 -= 1 Loop
Return E1 <= S And E2 <= S End Function <br>Асимптотика линейная. В худшем случае (при одинаковых строках) делается по два полных прохода по каждой из строк.
