碼迷,www.tparu.icu
吉利平特名人堂 > 編程語言 > 詳細

二期必开平特肖:72. Edit Distance (JAVA)

時間:2019-05-23 18:21:34      閱讀:47      評論:0      收藏:0      [點我收藏+]

吉利平特名人堂 www.tparu.icu 標簽:put   move   lan   NPU   number   execution   question   return   bsp   

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

  1. Insert a character
  2. Delete a character
  3. Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace ‘h‘ with ‘r‘)
rorse -> rose (remove ‘r‘)
rose -> ros (remove ‘e‘)

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove ‘t‘)
inention -> enention (replace ‘i‘ with ‘e‘)
enention -> exention (replace ‘n‘ with ‘x‘)
exention -> exection (replace ‘n‘ with ‘c‘)
exection -> execution (insert ‘u‘)
 

使用遞歸會造成Time limit exceeded

class Solution {
    public int minDistance(String word1, String word2) {
        StringBuffer strBuf1 = new StringBuffer(word1);
        StringBuffer strBuf2 = new StringBuffer(word2);
        
        return dfs(strBuf1,strBuf2,0,0,0);
    }
    
    public int insert(StringBuffer strBuf1, StringBuffer strBuf2, int i1, int i2, int depth){
        strBuf1.insert(i1, strBuf2.charAt(i2));
        int ret = dfs(strBuf1,strBuf2,i1+1, i2+1,depth+1);
        strBuf1.deleteCharAt(i1); //recover
        return ret;
    }
    
    public int delete(StringBuffer strBuf1, StringBuffer strBuf2, int i1, int i2, int depth){
        Character ch = strBuf1.charAt(i1);
        strBuf1.deleteCharAt(i1);
        int ret = dfs(strBuf1,strBuf2,i1, i2,depth+1);
        strBuf1.insert(i1,ch); //recover;
        return ret;
    }
    
    public int replace(StringBuffer strBuf1, StringBuffer strBuf2, int i1, int i2, int depth){
        Character ch = strBuf1.charAt(i1);
        strBuf1.setCharAt(i1, strBuf2.charAt(i2));
        int ret = dfs(strBuf1,strBuf2,i1+1, i2+1,depth+1);
        strBuf1.setCharAt(i1, ch);
        return ret;
    }
    
    private int dfs(StringBuffer strBuf1, StringBuffer strBuf2, int i1, int i2, int depth){
        while(i1 < strBuf1.length() && i2 < strBuf2.length() && strBuf1.charAt(i1) == strBuf2.charAt(i2)){
            i1++;
            i2++;
        }
        
        if(i1 == strBuf1.length() && i2 == strBuf2.length()) return depth;
        if(i1 == strBuf1.length()) return depth+strBuf2.length()-i2;
        if(i2 == strBuf2.length()) return depth+strBuf1.length()-i1;

        int ret = insert(strBuf1,strBuf2,i1,i2,depth);
        ret = Math.min(ret,delete(strBuf1,strBuf2,i1,i2,depth));
        ret = Math.min(ret,replace(strBuf1,strBuf2,i1,i2,depth));

        return ret;
        
    }
    
}

 

72. Edit Distance (JAVA)

標簽:put   move   lan   NPU   number   execution   question   return   bsp   

原文地址:https://www.cnblogs.com/qionglouyuyu/p/10913547.html

(0)
(0)
   
舉報
評論 一句話評論(0
登錄后才能評論!
? 2014 吉利平特名人堂 版權所有 京ICP備13008772號-2
迷上了代碼!
新时时走势图500 彩神软件 北京pk10怎么才能挣钱 福建时时开奖列表 黑龙江时时三星综合走势图 重庆时时计划人工在线 北京pk赛车走势图 重庆时时开奖官方同步 pk10单双免费计划软件 90win足球即时比分 梅苏特厄齐尔 后三不定位1胆的技巧 北京塞车计划网页 幸运飞船计划软件下载 重庆时时彩走势 排列三组六稳赚的投注技巧