資訊專欄INFORMATION COLUMN
摘要：題目地址題目描述給定兩個單詞和，計算出將轉換成所使用的最少操作數。那么答案則為那么如何求呢也就是轉移方程。由定義可以知道空字符串變成任意長度字符串的代價為該字符串的長度，也就是說。若，那么這里的解釋是，增加了一個比較對象，變成。
題目地址：
https://leetcode-cn.com/probl...
題目描述：
給定兩個單詞 word1 和 word2，計算出將 word1 轉換成 word2 所使用的最少操作數 。
你可以對一個單詞進行如下三種操作：
1.插入一個字符
2.刪除一個字符
3.替換一個字符
解答：
這一題用動態規劃，dpi表示word1中0到i的字符所組成的字符串到word2中0到j的字符所組成的字符串的編輯距離。
那么答案則為dpword1.length
那么如何求dpi呢？也就是轉移方程。由定義可以知道空字符串變成任意長度字符串的代價為該字符串的長度，也就是說dp0 = j+1,dpi = i+1。這里的i，j最大分別為word1和word2的長度-1。
對于dpi,若word1[i] != word2[j]，那么dpi = 1 + min(dpi-1,dpi),這里的解釋為刪除word1[i]或者刪除word2[j],并且比較word1[0-i-1]變成word2[0-j]和word1[0-i]變成word2[0-j-1]的大小，選擇小的那個。
若word1[i] == word2[j]，那么dpi = min(dpi-1,1 + min(dpi-1,dpi))這里的解釋是，增加了一個比較對象，word1[0-i-1]變成word2[0-j-1]。
java ac代碼：
class Solution {
public int minDistance(String word1, String word2) {
if(word1.length() == 0||word2.length() == 0)return Math.max(word1.length(),word2.length());
int[][]dp = new int[word1.length()+1][word2.length()+1];
for(int i = 0;i <= word1.length();i++)
dp[i][0] = i;
for(int j = 0;j <= word2.length();j++)
dp[0][j] = j;
for(int i = 1;i <= word1.length();i++)
for(int j = 1;j <= word2.length();j++)
{
int ans = 1+Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]);
if(word1.charAt(i-1) == word2.charAt(j-1))
ans = Math.min(ans,dp[i-1][j-1]);
dp[i][j] = ans;
}
return dp[word1.length()][word2.length()];
}
}
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/73297.html
摘要：圖因此可以成為樹，在所有可能的樹中，具有最小高度的樹被稱為最小高度樹。給出這樣的一個圖，寫出一個函數找到所有的最小高度樹并返回他們的根節點。因此使用一個數組代表每個節點的入度，若入度為就是葉子節點。 題目地址：https://leetcode-cn.com/probl...題目描述： 對于一個具有樹特征的無向圖，我們可選擇任何一個節點作為根。圖因此可以成為樹，在所有可能的樹中，具有最小...
摘要：關于遞歸這里提一兩點遞歸基本有這幾步遞歸的模板，終止條件，遞歸調用，邏輯處理。 ?作者簡介：大家好，我是車神哥，府學路18號的車神? ?個人主頁：應無所住而生...
摘要：對于每個氣球，提供的輸入是水平方向上，氣球直徑的開始和結束坐標。可以射出的弓箭的數量沒有限制。弓箭一旦被射出之后，可以無限地前進。我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數量。解答這是一道區間覆蓋問題，不太好說清楚，利用模板即可。 題目地址：https://leetcode-cn.com/probl...題目描述：在二維空間中有許多球形的氣球。對于每個氣球，提供的輸入是水平方...
摘要：有效二叉搜索樹定義如下節點的左子樹只包含小于當前節點的數。所有左子樹和右子樹自身必須也是二叉搜索樹。而我們二叉搜索樹保證了左子樹的節點的值均小于根節點的值，根節點的值均小于右子樹的值，因此中序遍歷以后得到的序列一定是升序序列。 ...
閱讀 2060·2023-04-25 17:48
閱讀 3577·2021-09-22 15:37
閱讀 2932·2021-09-22 15:36
閱讀 5863·2021-09-22 15:06
閱讀 1634·2019-08-30 15:53
閱讀 1422·2019-08-30 15:52
閱讀 706·2019-08-30 13:48
閱讀 1116·2019-08-30 12:44
