{"id":201557,"date":"2020-11-24T16:08:34","date_gmt":"2020-11-24T08:08:34","guid":{"rendered":"http:\/\/4563.org\/?p=201557"},"modified":"2020-11-24T16:08:34","modified_gmt":"2020-11-24T08:08:34","slug":"google-%e9%9d%a2%e8%af%95%e9%a2%98%ef%bc%9a%e7%bc%96%e8%be%91%e8%b7%9d%e7%a6%bb","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=201557","title":{"rendered":"Google \u9762\u8bd5\u9898\uff1a\u7f16\u8f91\u8ddd\u79bb"},"content":{"rendered":"
\n
\n
\n

Google \u9762\u8bd5\u9898\uff1a\u7f16\u8f91\u8ddd\u79bb <\/h1>\n

<\/p>\n

\n
\u8cc7\u6df1\u5927\u4f6c : zzzrf <\/span> <\/i> 0<\/span> <\/div>\n
<\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n
<\/p>\n

\u7ed9\u51fa\u4e24\u4e2a\u5355\u8bcd word1 \u548c word2\uff0c\u8ba1\u7b97\u51fa\u5c06 word1 \u8f6c\u6362\u4e3a word2 \u7684\u6700\u5c11\u64cd\u4f5c\u6b21\u6570\u3002 \u4f60\u603b\u5171\u4e09\u79cd\u64cd\u4f5c\u65b9\u6cd5\uff1a<\/p>\n

    \n
  • \u63d2\u5165\u4e00\u4e2a\u5b57\u7b26<\/li>\n
  • \u5220\u9664\u4e00\u4e2a\u5b57\u7b26<\/li>\n
  • \u66ff\u6362\u4e00\u4e2a\u5b57\u7b26<\/li>\n<\/ul>\n

    \u5728\u7ebf\u8bc4\u6d4b\u5730\u5740<\/p>\n

    \u6837\u4f8b 1:<\/h2>\n
    \u8f93\u5165:  \"horse\" \"ros\" \u8f93\u51fa: 3 \u89e3\u91ca:  horse -> rorse (\u66ff\u6362 'h' \u4e3a 'r') rorse -> rose (\u5220\u9664 'r') rose -> ros (\u5220\u9664 'e') <\/code><\/pre>\n
    \u6837\u4f8b 2:<\/h2>\n
    \u8f93\u5165:  \"intention\" \"execution\" \u8f93\u51fa: 5 \u89e3\u91ca:  intention -> inention (\u5220\u9664 't') inention -> enention (\u66ff\u6362 'i' \u4e3a 'e') enention -> exention (\u66ff\u6362 'n' \u4e3a 'x') exention -> exection (\u66ff\u6362 'n' \u4e3a 'c') exection -> execution (\u63d2\u5165 'u') <\/code><\/pre>\n
    \u7b97\u6cd5\uff1aDP<\/h2>\n
    \u7ecf\u5178\u7684\u4e8c\u7ef4 dp \u3002 \u5b9a\u4e49 f[i][j]\u4e3a word1 \u524d i \u4e2a\u5b57\u7b26\u5230 word2 \u7684\u524d j \u4e2a\u5b57\u7b26\u7684\u8f6c\u5316\u7684\u6700\u5c0f\u6b65\u3002 \u63a5\u7740\uff0c\u6211\u4eec\u6765\u8003\u8651\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\u3002<\/p>\n
      \n
    • \u5047\u8bbe\u5bf9\u4e8e f[i][j]\u4ee5\u524d\u7684\u4e4b\u90fd\u5df2\u77e5\uff0c\u8003\u8651 fi \u7684\u60c5\u5f62\u3002<\/li>\n
    • \u82e5 word1[i] = word2[j]\uff0c\u90a3\u4e48\u8bf4\u660e\u53ea\u8981 word1 \u7684\u524d i-1 \u4e2a\u80fd\u8f6c\u6362\u5230 word2 \u7684\u524d j-1 \u4e2a\u5373\u53ef\uff0c\u6240\u4ee5 f[i][j] = f[i-1][j-1]<\/li>\n
    • \u53cd\u4e4b\uff0c\u82e5\u4e0d\u7b49\uff0c\u6211\u4eec\u5c31\u8981\u8003\u8651\u4ee5\u4e0b\u60c5\u5f62\u4e86\u3002<\/li>\n
    • \u7ed9 word1 \u63d2\u5165\u4e00\u4e2a\u548c word2 \u6700\u540e\u7684\u5b57\u6bcd\u76f8\u540c\u7684\u5b57\u6bcd\uff0c\u8fd9\u65f6 word1 \u548c word2 \u7684\u6700\u540e\u4e00\u4e2a\u5b57\u6bcd\u5c31\u4e00\u6837\u4e86\uff0c\u6b64\u65f6\u7f16\u8f91\u8ddd\u79bb\u7b49\u4e8e 1 \uff08\u63d2\u5165\u64cd\u4f5c\uff09 + \u63d2\u5165\u524d\u7684 word1 \u5230 word2 \u53bb\u6389\u6700\u540e\u4e00\u4e2a\u5b57\u6bcd\u540e\u7684\u7f16\u8f91\u8ddd\u79bb f[i][j – 1] + 1<\/li>\n
    • \u5220\u9664 word1 \u7684\u6700\u540e\u4e00\u4e2a\u5b57\u6bcd\uff0c\u6b64\u65f6\u7f16\u8f91\u8ddd\u79bb\u7b49\u4e8e 1 \uff08\u5220\u9664\u64cd\u4f5c\uff09 + word1 \u53bb\u6389\u6700\u540e\u4e00\u4e2a\u5b57\u6bcd\u5230 word2 \u7684\u7f16\u8f91\u8ddd\u79bb f[i – 1][j] + 1<\/li>\n
    • \u628a word1 \u7684\u6700\u540e\u4e00\u4e2a\u5b57\u6bcd\u66ff\u6362\u6210 word2 \u7684\u6700\u540e\u4e00\u4e2a\u5b57\u6bcd\uff0c\u6b64\u65f6\u7f16\u8f91\u8ddd\u79bb\u7b49\u4e8e 1 \uff08\u66ff\u6362\u64cd\u4f5c\uff09 + word1 \u548c word2 \u53bb\u6389\u6700\u540e\u4e00\u4e2a\u5b57\u6bcd\u7684\u7f16\u8f91\u8ddd\u79bb\u3002\u4e3a f[i – 1][j – 1] + 1<\/li>\n
    • \u4e09\u8005\u53d6\u6700\u5c0f\u503c\u5373\u53ef\u3002<\/li>\n<\/ul>\n
      \u590d\u6742\u5ea6\u5206\u6790<\/h2>\n
        \n
      • \u65f6\u95f4\u590d\u6742\u5ea6 O(n^2)\n
          \n
        • \u4e8c\u7ef4 dp<\/li>\n<\/ul>\n<\/li>\n
        • \u7a7a\u95f4\u590d\u6742\u5ea6 O(n^2)\n
            \n
          • \u9700\u8981\u4fdd\u5b58\u4e8c\u7ef4\u7684\u72b6\u6001\u6570<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n
            public class Solution {     public int minDistance(String word1, String word2) {         int n = word1.length();         int m = word2.length();          int[][] dp = new int[n+1][m+1];         for (int i = 0; i < m + 1; i++) {             dp[0][i] = i;          }          for (int i = 0; i < n + 1; i++) {             dp[i][0] = i;         }          for (int i = 1; i < n + 1; i++) {             for (int j = 1; j < m + 1; j++) {                 if (word1.charAt(i - 1) == word2.charAt(j - 1)) {                     dp[i][j] = dp[i - 1][j - 1];                 }else{                     dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));                 }             }         }         return dp[n][m];     } } <\/code><\/pre>\n<\/p><\/div>\n
             \u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (0<\/span>)        <\/div>\n
             <\/div>\n<\/p><\/div>\n<\/p><\/div>\n
              \n
            • \n","protected":false},"excerpt":{"rendered":"
              Google \u9762\u8bd5\u9898\uff1a\u7f16\u8f91\u8ddd\u79bb \u8cc7…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/201557"}],"collection":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=201557"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/201557\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=201557"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=201557"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=201557"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}