Рубрики

Проверьте, является ли расстояние редактирования между двумя строками одним

Редактирование между двумя строками является одним из следующих изменений.

  1. Добавить персонажа
  2. Удалить персонажа
  3. Изменить персонажа

Учитывая две строки s1 и s2, найдите, можно ли преобразовать s1 в s2 ровно с одним редактированием. Ожидаемая сложность по времени составляет O (m + n), где m и n — длины двух строк.

Примеры:

Input:  s1 = "geeks", s2 = "geek"
Output: yes
Number of edits is 1

Input:  s1 = "geeks", s2 = "geeks"
Output: no
Number of edits is 0

Input:  s1 = "geaks", s2 = "geeks"
Output: yes
Number of edits is 1

Input:  s1 = "peaks", s2 = "geeks"
Output: no
Number of edits is 2

Простое решение — найти расстояние редактирования с помощью динамического программирования . Если расстояние равно 1, вернуть true, иначе вернуть false. Временная сложность этого решения составляет O (n 2 )

Эффективное решение заключается в одновременном прохождении обеих строк и отслеживании количества различных символов. Ниже приведен полный алгоритм.

Let the input strings be s1 and s2 and lengths of input 
strings be m and n respectively.

1) If difference between m an n is more than 1, 
     return false.
2) Initialize count of edits as 0.
3) Start traversing both strings from first character.
    a) If current characters don't match, then
       (i)   Increment count of edits
       (ii)  If count becomes more than 1, return false
       (iii) If length of one string is more, then only
             possible  edit is to remove a character.
             Therefore, move ahead in larger string.
       (iv)  If length is same, then only possible edit
             is to  change a character. Therefore, move
             ahead in both strings. 
    b) Else, move ahead in both strings. 

Ниже приведена реализация вышеуказанной идеи:

C ++

// C ++ программа для проверки, если заданы две строки
// на расстоянии один.
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает true, если редактировать расстояние между s1 и
// s2 один, иначе ложь

bool isEditDistanceOne(string s1, string s2)

{

    // Находим длины заданных строк

    int m = s1.length(), n = s2.length();

  

    // Если разница между длинами больше чем

    // 1, тогда строки не могут быть на одном расстоянии

    if (abs(m - n) > 1)

        return false;

  

    int count = 0; // Количество правок

  

    int i = 0, j = 0;

    while (i < m && j < n)

    {

        // Если текущие символы не совпадают

        if (s1[i] != s2[j])

        {

            if (count == 1)

                return false;

  

            // Если длина одной строки

            // больше, тогда возможно только редактирование

            // удалить символ

            if (m > n)

                i++;

            else if (m< n)

                j++;

            else // Если длины обеих строк одинаковы

            {

                i++;

                j++;

            }

              

            // Увеличение количества правок

            count++;

        }

  

        else // Если текущие символы совпадают

        {

            i++;

            j++;

        }

    }

  

    // Если последний символ является лишним в любой строке

    if (i < m || j < n)

        count++;

  

    return count == 1;

}

  
// Драйвер программы

int main()

{

   string s1 = "gfg";

   string s2 = "gf";

   isEditDistanceOne(s1, s2)?

           cout << "Yes": cout << "No";

   return 0;

}

Джава

// Java-программа для проверки, если дано
// две строки на расстоянии один.

class GFG 

{
// Возвращает true, если расстояние редактирования
// между s1 и s2 один, иначе ложь

static boolean isEditDistanceOne(String s1,

                                 String s2)

{

    // Находим длины заданных строк

    int m = s1.length(), n = s2.length();

  

    // Если разница между длинами

    // больше 1, тогда строки не могут

    // быть на одном расстоянии

    if (Math.abs(m - n) > 1)

        return false;

  

    int count = 0; // Количество правок

  

    int i = 0, j = 0;

    while (i < m && j < n)

    {

        // Если текущие символы не совпадают

        if (s1.charAt(i) != s2.charAt(j))

        {

            if (count == 1)

                return false;

  

            // Если длина одной строки

            // больше, тогда возможно только редактирование

            // удалить символ

            if (m > n)

                i++;

            else if (m< n)

                j++;

            else // Iflengths обеих строк

                // такой же

            {

                i++;

                j++;

            }

              

            // Увеличение количества правок

            count++;

        }

  

        else // Если текущие символы совпадают

        {

            i++;

            j++;

        }

    }

  

    // Если последний символ лишний

    // в любой строке

    if (i < m || j < n)

        count++;

  

    return count == 1;

}

  
// код драйвера

public static void main (String[] args)

{

    String s1 = "gfg";

    String s2 = "gf";

    if(isEditDistanceOne(s1, s2))

        System.out.print("Yes");

    else

        System.out.print("No"); 

}
}

  
// Этот код предоставлен Anant Agarwal.

питон

# Python-программа для проверки, если заданы две строки
# на первом расстоянии

  
# Возвращает true, если расстояние редактирования между s1 и s2 равно
# один, иначе ложь

def isEditDistanceOne(s1, s2):

  

    # Найти длины заданных строк

    m = len(s1)

    n = len(s2)

  

    # Если разница между длинами больше 1,

    # тогда строки не могут быть на одном расстоянии

    if abs(m - n) > 1:

        return false

  

    count = 0    # Количество isEditDistanceOne

  

    i = 0

    j = 0

    while i < m and j < n:

        # Если текущие символы не совпадают

        if s1[i] != s2[j]:

            if count == 1:

                return false

  

            # Если длина одной строки

            # больше, тогда возможно только редактирование

            # удалить персонажа

            if m > n:

                i+=1

            elif m < n:

                j+=1

            else:    # Если длина обеих строк одинакова

                i+=1

                j+=1

  

            # Увеличение количества правок

            count+=1

  

        else:    # если текущие символы совпадают

            i+=1

            j+=1

  

    # если последний символ лишний в любой строке

    if i < m or j < n:

        count+=1

  

    return count == 1

  
# Драйверная программа

s1 = "gfg"

s2 = "gf"

if isEditDistanceOne(s1, s2):

    print "Yes"

else:

    print "No"

  
# Этот код предоставлен Bhavya Jain

C #

// C # программа для проверки, если дано
// две строки на расстоянии один.

using System;

  

class GFG

{

  
// Возвращает true, если расстояние редактирования
// между s1 и s2 один, иначе ложь

static bool isEditDistanceOne(String s1,

                              String s2)

{

      

    // Находим длины заданных строк

    int m = s1.Length, n = s2.Length;

  

    // Если разница между длинами

    // больше 1, тогда строки не могут

    // быть на одном расстоянии

    if (Math.Abs(m - n) > 1)

        return false;

  

        // Количество правок

        int count = 0;

        int i = 0, j = 0;

          

    while (i < m && j < n)

    {

        // Если текущие символы

        // не совпадают

        if (s1[i] != s2[j])

        {

            if (count == 1)

                return false;

  

            // Если длина одной строки

            // больше, тогда возможно только редактирование

            // удалить символ

            if (m > n)

                i++;

            else if (m< n)

                j++;

                  

             // Если длины обоих

             // строки одинаковые

            else

            {

                i++;

                j++;

            }

              

            // Увеличение количества правок

            count++;

        }

  

        // Если текущие символы совпадают

        else 

        {

            i++;

            j++;

        }

    }

  

    // Если последний символ лишний

    // в любой строке

    if (i < m || j < n)

        count++;

  

    return count == 1;

}

  
// Код драйвера

public static void Main ()

{

    String s1 = "gfg";

    String s2 = "gf";

    if(isEditDistanceOne(s1, s2))

        Console.WriteLine("Yes");

    else

        Console.WriteLine("No"); 

}
}

  
// Этот код предоставлен Sam007.

PHP

<?php
// PHP программа для проверки, если дано
// две строки на расстоянии один.

  
// Возвращает true, если расстояние редактирования
// между s1 и s2 один, иначе
// ложный

function isEditDistanceOne($s1, $s2)

{

      

    // Находим длины заданных строк

    $m = strlen($s1);

    $n = strlen($s2);

  

    // Если разница между

    // длина больше чем

    // 1, тогда строки не могут

    // быть на одном расстоянии

    if (abs($m - $n) > 1)

        return false;

  

    // Количество правок

    $count = 0; 

  

    $i = 0; $j = 0;

    while ($i < $m && $j < $n)

    {

        // Если текущие символы

        // не совпадают

        if ($s1[$i] != $s2[$j])

        {

            if ($count == 1)

                return false;

  

            // Если длина одной строки

            // больше, тогда возможно только редактирование

            // удалить символ

            if ($m > $n)

                $i++;

            else if ($m< $n)

                $j++;

                  

             // Если длины обоих

             // строки одинаковые

            else

            {

                $i++;

                $j++;

            }

              

            // Увеличение количества правок

            $count++;

        }

  

        // Если текущие символы

        // совпадение

        else 

        {

            $i++;

            $j++;

        }

    }

  

    // Если последний символ

    // дополнительно в любой строке

    if ($i < $m || $j < $n)

        $count++;

  

    return $count == 1;

}

  
// Код драйвера

$s1 = "gfg";

$s2 = "gf";

if(isEditDistanceOne($s1, $s2))

    echo "Yes";

else

    echo "No";

  
// Этот код предоставлен нитин митталь.
?>

Выход:

Yes

Временная сложность: O (n)
Вспомогательное пространство: O (1)

Спасибо Gaurav Ahirwar за предложенное выше решение.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Проверьте, является ли расстояние редактирования между двумя строками одним

0.00 (0%) 0 votes