首页 > 代码库 > 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 字符串编辑距离
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。