Рубрики

Изменить расстояние | DP-5

Даны две строки str1 и str2 и ниже операций, которые могут выполняться на str1. Найдите минимальное количество правок (операций), необходимых для преобразования 'str1' в 'str2'.

  1. Вставить
  2. удалять
  3. замещать

Все вышеперечисленные операции имеют одинаковую стоимость.

Примеры:

Input:   str1 = "geek", str2 = "gesek"
Output:  1
We can convert str1 into str2 by inserting a 's'.

Input:   str1 = "cat", str2 = "cut"
Output:  1
We can convert str1 into str2 by replacing 'a' with 'u'.

Input:   str1 = "sunday", str2 = "saturday"
Output:  3
Last three and first characters are same.  We basically
need to convert "un" to "atur".  This can be done using
below three operations. 
Replace 'n' with 'r', insert t, insert a

Каковы подзадачи в этом случае?
Идея состоит в том, чтобы обрабатывать все символы один за другим, начиная с левой или правой стороны обеих строк.
Давайте пройдем через правый угол, есть две возможности для каждой пары пройденных персонажей.

m: Length of str1 (first string)
n: Length of str2 (second string)
  1. Если последние символы двух строк одинаковы, делать нечего. Проигнорируйте последние символы и получите количество оставшихся строк. Таким образом, мы повторяем для длин m-1 и n-1.
  2. Иначе (если последние символы не совпадают), мы рассмотрим все операции над 'str1', рассмотрим все три операции над последним символом первой строки, рекурсивно вычисляем минимальную стоимость для всех трех операций и принимаем минимум три значения.
    1. Вставка: Recur для м и н-1
    2. Удалить: повтор для m-1 и n
    3. Заменить: Recur для m-1 и n-1

Ниже приведена реализация C ++ вышеупомянутого Наивного рекурсивного решения.

C ++

// Наивная рекурсивная программа на C ++ для поиска минимального числа
// операции для преобразования str1 в str2
#include<bits/stdc++.h>

using namespace std;

  
// Утилита для поиска минимум трех чисел

int min(int x, int y, int z)

{

   return min(min(x, y), z);

}

  

int editDist(string str1 , string str2 , int m ,int n)

{

    // Если первая строка пуста, единственный вариант

    // вставляем все символы второй строки в первую

    if (m == 0) return n;

  

    // Если вторая строка пуста, единственный вариант

    // удаляем все символы первой строки

    if (n == 0) return m;

  

    // Если последние символы двух строк совпадают, ничего

    // много сделать. Игнорировать последние символы и получить счет за

    // оставшиеся строки.

    if (str1[m-1] == str2[n-1])

        return editDist(str1, str2, m-1, n-1);

  

    // Если последние символы не совпадают, рассмотрим все три

    // операции над последним символом первой строки, рекурсивно

    // вычисляем минимальную стоимость для всех трех операций и принимаем

    // минимум три значения.

    return 1 + min ( editDist(str1,  str2, m, n-1),    // Вставить

                     editDist(str1,  str2, m-1, n),   // Удалять

                     editDist(str1,  str2, m-1, n-1) // Заменить

                   );

}

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

int main()

{

    // ваш код идет сюда

    string str1 = "sunday";

    string str2 = "saturday";

  

    cout << editDist( str1 , str2 , str1.length(), str2.length());

  

    return 0;

}

Джава

// Наивная рекурсивная Java-программа для поиска минимального числа
// операции для преобразования str1 в str2

class EDIST

{

    static int min(int x,int y,int z)

    {

        if (x<=y && x<=z) return x;

        if (y<=x && y<=z) return y;

        else return z;

    }

  

    static int editDist(String str1 , String str2 , int m ,int n)

    {

        // Если первая строка пуста, единственный вариант

    // вставляем все символы второй строки в первую

    if (m == 0) return n;

       

    // Если вторая строка пуста, единственный вариант

    // удаляем все символы первой строки

    if (n == 0) return m;

       

    // Если последние символы двух строк совпадают, ничего

    // много сделать. Игнорировать последние символы и получить счет за

    // оставшиеся строки.

    if (str1.charAt(m-1) == str2.charAt(n-1))

        return editDist(str1, str2, m-1, n-1);

       

    // Если последние символы не совпадают, рассмотрим все три

    // операции над последним символом первой строки, рекурсивно

    // вычисляем минимальную стоимость для всех трех операций и принимаем

    // минимум три значения.

    return 1 + min ( editDist(str1,  str2, m, n-1),    // Вставить

                     editDist(str1,  str2, m-1, n),   // Удалять

                     editDist(str1,  str2, m-1, n-1) // Заменить

                   );

    }

  

    public static void main(String args[])

    {

        String str1 = "sunday";

        String str2 = "saturday";

   

        System.out.println( editDist( str1 , str2 , str1.length(), str2.length()) );

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

питон

# Наивная рекурсивная программа Python для поиска минимального числа
# операции по преобразованию str1 в str2

def editDistance(str1, str2, m , n):

  

    # Если первая строка пуста, единственным вариантом является

    # вставить все символы второй строки в первую

    if m==0:

         return n

  

    # Если вторая строка пуста, единственным вариантом является

    # удалить все символы первой строки

    if n==0:

        return m

  

    # Если последние символы двух строк совпадают, ничего

    # много дел. Игнорировать последние символы и получить счет за

    # оставшиеся строки.

    if str1[m-1]==str2[n-1]:

        return editDistance(str1,str2,m-1,n-1)

  

    # Если последние символы не совпадают, рассмотрим все три

    # операций над последним символом первой строки, рекурсивно

    # рассчитать минимальную стоимость для всех трех операций и принять

    # минимум трех значений.

    return 1 + min(editDistance(str1, str2, m, n-1),    # Вставить

                   editDistance(str1, str2, m-1, n),    # Удалять

                   editDistance(str1, str2, m-1, n-1)    # Заменить

                   )

  
# Драйвер программы для проверки вышеуказанной функции

str1 = "sunday"

str2 = "saturday"

print editDistance(str1, str2, len(str1), len(str2))

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

C #

// Наивная рекурсивная программа на C # для
// найти минимальное количество операций
// конвертировать str1 в str2

using System;

  

class GFG

{

    static int min(int x, int y, int z)

    {

        if (x <= y && x <= z) return x;

        if (y <= x && y <= z) return y;

        else return z;

    }

  

    static int editDist(String str1 , String str2 , int m ,int n)

    {

        // Если первая строка пуста, единственный вариант

        // вставляем все символы второй строки в первую

        if (m == 0) return n;

          

        // Если вторая строка пуста, единственный вариант

        // удаляем все символы первой строки

        if (n == 0) return m;

          

        // Если последние символы двух строк совпадают, ничего

        // много сделать. Игнорировать последние символы и получить счет за

        // оставшиеся строки.

        if (str1[m - 1] == str2[n - 1])

            return editDist(str1, str2, m - 1, n - 1);

          

        // Если последние символы не совпадают, рассмотрим все три

        // операции над последним символом первой строки, рекурсивно

        // вычисляем минимальную стоимость для всех трех операций и принимаем

        // минимум три значения.

        return 1 + min ( editDist(str1, str2, m, n - 1), // Вставить

                        editDist(str1, str2, m - 1, n), // Удалять

                        editDist(str1, str2, m - 1, n - 1) // Заменить

                    );

    }

      

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

    public static void Main()

    {

        String str1 = "sunday";

        String str2 = "saturday";

        Console.WriteLine( editDist( str1 , str2 , str1.Length, 

                                                 str2.Length ));

    }

}

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

PHP

<?php 
// Наивная рекурсивная программа на Python
// найти минимальное количество операций
// конвертировать str1 в str2

function editDistance($str1, $str2

                      $m, $n)

    // Если первая строка пуста,

    // единственный вариант - вставить.

    // все символы секунды

    // строка в первую

    if ($m == 0)

        return $n

  

    // Если вторая строка пуста,

    // единственный вариант

    // удаляем все символы

    // первая строка

    if ($n == 0) 

        return $m

  

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

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

    // много сделать. Игнорировать последний

    // символы и счет

    // для оставшихся строк.

    if ($str1[$m - 1] == $str2[$n - 1])

    

        return editDistance($str1, $str2

                            $m - 1, $n - 1); 

    }

      

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

    // рассмотрим все три операции на

    // последний символ первой строки,

    // рекурсивно вычисляем минимальную стоимость

    // для всех трех операций и взять

    // минимум три значения.

  

    return 1 + min(editDistance($str1, $str2

                                $m, $n - 1), // Вставить

                   editDistance($str1, $str2

                                $m - 1, $n), // Удалять

                   editDistance($str1, $str2

                                $m - 1, $n - 1)); // Заменить

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

$str1 = "sunday";

$str2 = "saturday";

echo editDistance($str1, $str2, strlen($str1), 

                                strlen($str2)); 

  
// Этот код добавлен
// от Shivi_Aggarwal
?>


Выход:

3

Временная сложность вышеуказанного решения является экспоненциальной. В худшем случае мы можем выполнить O (3 м ) операций. Худший случай случается, когда ни один из символов двух строк не совпадает. Ниже приведена рекурсивная диаграмма вызовов для наихудшего случая.

Мы видим, что многие подзадачи решаются снова и снова, например, eD (2,2) вызывается три раза. Поскольку те же самые подзадачи вызываются снова, эта проблема имеет свойство Перекрывающиеся подзадачи. Таким образом, проблема редактирования расстояния имеет оба свойства (см. Это и это ) задачи динамического программирования. Как и другие типичные проблемы динамического программирования (DP), повторных вычислений с одинаковыми подзадачами можно избежать, создав временный массив, в котором хранятся результаты подзадач.

C ++

// Программа на C ++ для динамического программирования, чтобы найти минимум
// числовые операции для преобразования str1 в str2
#include<bits/stdc++.h>

using namespace std;

  
// Утилита для поиска минимум трех чисел

int min(int x, int y, int z)

{

    return min(min(x, y), z);

}

  

int editDistDP(string str1, string str2, int m, int n)

{

    // Создать таблицу для хранения результатов подзадач

    int dp[m+1][n+1];

  

    // Заполняем d [] [] снизу вверх

    for (int i=0; i<=m; i++)

    {

        for (int j=0; j<=n; j++)

        {

            // Если первая строка пуста, единственный вариант

            // вставляем все символы второй строки

            if (i==0)

                dp[i][j] = j;  // Мин. операции = j

  

            // Если вторая строка пуста, единственный вариант -

            // удаляем все символы второй строки

            else if (j==0)

                dp[i][j] = i; // Мин. операции = я

  

            // Если последние символы одинаковы, игнорируем последний символ

            // и повторить оставшуюся строку

            else if (str1[i-1] == str2[j-1])

                dp[i][j] = dp[i-1][j-1];

  

            // Если последний символ отличается, рассмотрим все

            // возможности и найти минимум

            else

                dp[i][j] = 1 + min(dp[i][j-1],  // Вставить

                                   dp[i-1][j],  // Удалять

                                   dp[i-1][j-1]); // Заменить

        }

    }

  

    return dp[m][n];

}

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

int main()

{

    // ваш код идет сюда

    string str1 = "sunday";

    string str2 = "saturday";

  

    cout << editDistDP(str1, str2, str1.length(), str2.length());

  

    return 0;

}

Джава

// Java-программа на основе динамического программирования, чтобы найти минимум
// числовые операции для преобразования str1 в str2

class EDIST

{

    static int min(int x,int y,int z)

    {

        if (x <= y && x <= z) return x;

        if (y <= x && y <= z) return y;

        else return z;

    }

  

    static int editDistDP(String str1, String str2, int m, int n)

    {

        // Создать таблицу для хранения результатов подзадач

        int dp[][] = new int[m+1][n+1];

       

        // Заполняем d [] [] снизу вверх

        for (int i=0; i<=m; i++)

        {

            for (int j=0; j<=n; j++)

            {

                // Если первая строка пуста, единственный вариант

                // вставляем все символы второй строки

                if (i==0)

                    dp[i][j] = j;  // Мин. операции = j

       

                // Если вторая строка пуста, единственный вариант -

                // удаляем все символы второй строки

                else if (j==0)

                    dp[i][j] = i; // Мин. операции = я

       

                // Если последние символы одинаковы, игнорируем последний символ

                // и повторить оставшуюся строку

                else if (str1.charAt(i-1) == str2.charAt(j-1))

                    dp[i][j] = dp[i-1][j-1];

       

                // Если последний символ отличается, рассмотрим все

                // возможности и найти минимум

                else

                    dp[i][j] = 1 + min(dp[i][j-1],  // Вставить

                                       dp[i-1][j],  // Удалять

                                       dp[i-1][j-1]); // Заменить

            }

        }

   

        return dp[m][n];

    }

  

      

  

    public static void main(String args[])

    {

        String str1 = "sunday";

        String str2 = "saturday";

        System.out.println( editDistDP( str1 , str2 , str1.length(), str2.length()) );

    }

}/ * Этот код предоставлен Раджатом Мишрой * /

питон

# Программа Python, основанная на динамическом программировании, для редактирования
# проблема расстояния

def editDistDP(str1, str2, m, n):

    # Создать таблицу для хранения результатов подзадач

    dp = [[0 for x in range(n+1)] for x in range(m+1)]

  

    # Заполните d [] [] снизу вверх

    for i in range(m+1):

        for j in range(n+1):

  

            # Если первая строка пуста, единственным вариантом является

            # вставить все символы второй строки

            if i == 0:

                dp[i][j] = j    # Мин. операции = j

  

            # Если вторая строка пуста, единственным вариантом является

            # удалить все символы второй строки

            elif j == 0:

                dp[i][j] = i    # Мин. операции = я

  

            # Если последние символы одинаковы, игнорировать последний символ

            # и повторить оставшуюся строку

            elif str1[i-1] == str2[j-1]:

                dp[i][j] = dp[i-1][j-1]

  

            # Если последний символ отличается, рассмотрим все

            # возможности и найти минимум

            else:

                dp[i][j] = 1 + min(dp[i][j-1],        # Вставить

                                   dp[i-1][j],        # Удалять

                                   dp[i-1][j-1])    # Заменить

  

    return dp[m][n]

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

str1 = "sunday"

str2 = "saturday"

  

print(editDistDP(str1, str2, len(str1), len(str2)))

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

C #

// Динамическое программирование на основе
// C # программа для поиска минимума
// номер операции для
// конвертируем str1 в str2

using System;

  

class GFG

{

    static int min(int x, int y, int z)

    {

        if (x <= y && x <= z) return x;

        if (y <= x && y <= z) return y;

        else return z;

    }

  

    static int editDistDP(String str1, String str2, int m, int n)

    {

        // Создать таблицу для хранения

        // результаты подзадач

        int [,]dp = new int[m + 1,n + 1];

      

        // Заполняем d [] [] снизу вверх

        for (int i = 0; i <= m; i++)

        {

            for (int j = 0; j <= n; j++)

            {

                // Если первая строка пуста, единственный вариант

                // вставляем все символы второй строки

                if (i == 0)

                  

                    // Мин. операции = j

                    dp[i, j] = j; 

      

                // Если вторая строка пуста, единственный вариант -

                // удаляем все символы второй строки

                else if (j == 0)

                       

                     // Мин. операции = я

                    dp[i,j] = i; 

      

                // Если последние символы одинаковы, игнорируем последний символ

                // и повторить оставшуюся строку

                else if (str1[i - 1] == str2[j - 1])

                    dp[i, j] = dp[i - 1, j - 1];

      

                // Если последний символ отличается, рассмотрим все

                // возможности и найти минимум

                else

                    dp[i, j] = 1 + min(dp[i, j - 1], // Вставить

                                    dp[i - 1, j], // Удалять

                                    dp[i - 1, j - 1]); // Заменить

            }

        }

  

        return dp[m, n];

    }

  

      

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

    public static void Main()

    {

        String str1 = "sunday";

        String str2 = "saturday";

        Console.Write( editDistDP( str1 , str2 , str1.Length, 

                                               str2.Length ));

    }

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

PHP

<?php
// Динамическое программирование на основе
// Python программа для редактирования
// проблема расстояния

function editDistDP($str1, $str2

                    $m, $n)


// Заполняем d [] [] снизу вверх

for ($i = 0; $i <= $m; $i++) 

{  

    for ($j = 0; $j <= $n; $j++) 

    

  

        // Если первая строка пуста,

        // единственный вариант - вставить

        // все символы второй строки

        if ($i == 0) 

            $dp[$i][$j] = $j ; // Мин. операции = j

  

        // Если вторая строка пуста,

        // единственный вариант - удалить

        // все символы второй строки

        else if($j == 0) 

            $dp[$i][$j] = $i; // Мин. операции = я

  

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

        // игнорируем последний символ и повторяем

        // для оставшейся строки

        else if($str1[$i - 1] == $str2[$j - 1]) 

            $dp[$i][$j] = $dp[$i - 1][$j - 1];

  

        // Если последний символ отличается,

        // рассмотреть все возможности и

        // найти минимум

        else

        

            $dp[$i][$j] = 1 + min($dp[$i][$j - 1],     // Вставить

                                  $dp[$i - 1][$j],     // Удалять

                                  $dp[$i - 1][$j - 1]); // Заменить

        }

    }

}

return $dp[$m][$n] ;

}

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

$str1 = "sunday";

$str2 = "saturday";

  

echo editDistDP($str1, $str2, strlen($str1), 

                              strlen($str2));

  
// Этот код добавлен
// от Shivi_Aggarwal
?>

Выход:

3

Сложность времени: O (mxn)
Вспомогательное пространство: O (mxn)

Приложения : Есть много практических применений алгоритма редактирования расстояния, для примера обратитесь к Lucene API. Другой пример, отобразить все слова в словаре, которые находятся рядом с заданным словом неправильно написанным словом.

Спасибо Вивеку Кумару за предложение обновлений.

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

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

Изменить расстояние | DP-5

0.00 (0%) 0 votes