程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode筆記:Edit Distance

leetcode筆記:Edit Distance

編輯:C++入門知識

leetcode筆記:Edit Distance


一. 題目描述

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

Insert a character
Delete a character
Replace a character

二. 題目分析

給定兩個字符串word1和word2,算出講word1轉化成word2所需的最少編輯操作次數。允許的編輯操作包括以下三種:

將一個字符替換成另一個字符
在字符串中插入一個字符
刪除字符串中的一個字符

例如將A(abc)轉成B(acbc):

你可選擇以下操作:
acc (b→c)替換
acb (c→b)替換
acbc (→c)插入

這不是最少編輯次數,因為其實只需要刪除第二個字符c就可以了,這樣只需操作一次。

使用i表示字符串word1的下標(從下標1開始),使用j表示字符串word2的下標。 用k[i][j]來表示word1[1, ... , i]word2[1, ... , j]之間的最少編輯操作數。則有以下規律:

k[i][0] = i;
k[0][j] = j;
k[i][j] = k[i - 1][j - 1] (if word1[i] == word2[j])
k[i][j] = min(k[i - 1][j - 1],
              k[i][j - 1],
              k[i - 1][j]) + 1  (if word1[i] != word2[j])

三. 示例代碼

#include 
#include 
#include 

using namespace std;

class Solution
{
public:
    int minDistance(const string &word1, const string &word2)
    {
        const size_t m = word1.size() + 1;
        const size_t n = word2.size() + 1;

        vector > k(m, vector(n));

        for (size_t i = 0; i < m; ++i)
            k[i][0] = i;

        for (size_t j = 0; j < n; ++j)
            k[0][j] = j;

        for (size_t i = 1; i < m; ++i)
        {
            for (size_t j = 1; j < n; ++j)
            {
                if (word1[i - 1] == word2[j - 1])
                    k[i][j] = k[i - 1][j - 1];
                else
                    k[i][j] = min(k[i - 1][j - 1], min(k[i - 1][j], k[i][j - 1])) + 1;
            }
        }
        return k[m - 1][n - 1];
    }
};

這裡寫圖片描述

四. 小結

動態規劃的經典題目,要快速寫出狀態轉移方程還是有點難度的。

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved