2

kedebug · kedebug · commit cb66fb5ed4d3 · 2014-04-25T10:03:03.000+08:00
diff --git a/EditDistance/EditDistance.cpp b/EditDistance/EditDistance.cpp
@@ -1,26 +1,23 @@
 class Solution {
 public:
     int minDistance(string word1, string word2) {
-        // Start typing your C/C++ solution below
-        // DO NOT write int main() function
-        
-        int len1 = word1.size();
-        int len2 = word2.size();
-        
-        for (int i = 0; i <= max(len1, len2); i++)
-            F[i][0] = F[0][i] = i;
-            
-        for (int i = 1; i <= len1; i++) {
-            for (int j = 1; j <= len2; j++) {
-                if (word1[i-1] == word2[j-1])
-                    F[i][j] = F[i-1][j-1];
-                else
-                    F[i][j] = min(F[i-1][j-1], min(F[i-1][j], F[i][j-1])) + 1;
+        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
+        for (int i = 1; i <= word1.size(); i++) {
+            dp[i][0] = i;
+        }
+        for (int j = 1; j <= word2.size(); j++) {
+            dp[0][j] = j;
+        }
+        for (int i = 1; i <= word1.size(); i++) {
+            for (int j = 1; j <= word2.size(); j++) {
+                if (word1[i-1] == word2[j-1]) {
+                    dp[i][j] = dp[i-1][j-1];
+                } else {
+                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1;
+                    dp[i][j] = min(dp[i][j], dp[i-1][j-1] + 1);
+                }
             }
         }
-        return F[len1][len2];
+        return dp[word1.size()][word2.size()];
     }
-private:
-    static const int MAXN = 1010;
-    int F[MAXN][MAXN];
-};
+};
