首页 > 代码库 > Leetcode:Edit Distance 字符串编辑距离

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:a) Insert a characterb) Delete a characterc) Replace a character

 

解析:

典型动态规划题.

设 distance[i,j]表示 word1[i]和word2[j]之间的编辑距离

1. 当word1[i] == word2[j]时,则 distance[i,j] = distance[i-1, j-1]

2. 当word1[i] 不等于 word2[j]时,分三种情况,分别对应三种操作

    

word1插入1个字符,即 distance[i, j] = distance[i, j - 1] + 1word1删除1个字符,即 distance[i, j] = distance[i - 1, j] + 1word1替换1个字符,即 distance[i, j] = distance[i - 1, j - 1] + 1

 

class Solution {public:    int minDistance(string word1, string word2) {        if (word1.size() == 0) return word2.size();        if (word2.size() == 0) return word1.size();                int rowNum = word1.size() + 1;        int colNum = word2.size() + 1;        std::vector<std::vector<int>> distance(rowNum, std::vector<int>(colNum, 0));        for (int i = 0; i < rowNum; ++i) {            distance.at(i).at(0) = i;        }        for (int j = 0; j < colNum; ++j) {            distance.at(0).at(j) = j;        }                for (int i = 1; i < rowNum; ++i) {            for (int j = 1; j < colNum; ++j) {                if (word1.at(i - 1) == word2.at(j - 1)) {                    distance.at(i).at(j) = distance.at(i - 1).at(j - 1);                } else {                    int deleteCost = distance.at(i - 1).at(j) + 1;                    int insertCost = distance.at(i).at(j - 1) + 1;                    int replaceCost = distance.at(i - 1).at(j - 1) + 1;                    distance.at(i).at(j) = std::min(deleteCost, std::min(insertCost, replaceCost));                }            }        }        return distance.at(word1.size()).at(word2.size());    }};

 

注意:

distance二维矩阵的设定,行和列都是对应字符串长度加1

distance二维矩阵的 0行 和 0列的初始化,边界情况

Leetcode:Edit Distance 字符串编辑距离