首页 > 试题广场 >

最小操作数

[编程题]最小操作数

热度指数：2059 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个原串和目标串，能对源串进行如下操作：

1.在给定位置插入一个字符

2.替换任意字符

3.删除任意字符要求完成一下函数，返回最少的操作数，使得源串进行这些操作后等于目标串。源串和目标串长度都小于2000。

算法知识视频讲解

喜刷刷

这个考的是LD算法（Levenshtein Distance）又称为编辑距离算法（Edit Distance）。

代码参考以下链接，稍作修改

http://www.cnblogs.com/biyeymyhjob/archive/2012/09/28/2707343.html

int mini(int a, int b) {
return a<b? a: b;
}

int minOperationCount(string source, string target) {
int max1 = source.size();
int max2 = target.size();

        int **ptr = new int*[max1 + 1];
        for(int i = 0; i < max1 + 1 ;i++)
            ptr[i] = new int[max2 + 1];

for(int i = 0 ;i < max1 + 1 ;i++)
ptr[i][0] = i;

for(int i = 0 ;i < max2 + 1;i++)
ptr[0][i] = i;

        for(int i = 1 ;i < max1 + 1 ;i++)
            for(int j = 1 ;j< max2 + 1; j++) {
                int temp = mini(ptr[i-1][j] + 1, ptr[i][j-1] + 1);
                ptr[i][j] = mini(temp,
                         ptr[i-1][j-1] + (source[i-1] != target[j-1]));
            }

int dis = ptr[max1][max2];

        for(int i = 0; i < max1 + 1; i++) {
            delete[] ptr[i];
            ptr[i] = NULL;
        }

delete[] ptr;
ptr = NULL;

return dis;
}

编辑于 2015-08-09 15:18:42 回复(1)

asdf

package com.yuzhouwan.changeSourceString;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

/**
*
* 给定一个原串和目标串，能对源串进行如下操作：<br>
* 1.在给定位置插入一个字符 <br>
* 2.替换任意字符 <br>
* 3.删除任意字符要求完成一下函数，返回最少的操作数，使得源串进行这些操作后等于目标串。源串和目标串长度都小于2000。<br>
*
* @author asdf2015
*
*/
public class ChangeStringTest {

   /**
   * 返回从源字符串到目标字符串的最小操作数 source: 源字符串 target：目标字符串返回：最小操作数
   */
   public int minOperationCount(String source, String target) {
       int operator = 0;
       char[] sChars = source.toCharArray();
       char[] tChars = target.toCharArray();

       int sLen = sChars.length;
       int tLen = tChars.length;
       int len = sLen > tLen ? sLen : tLen;

       if (sLen == 0 || tLen == 0)
           return len;

       for (int j = 0, i = 0; i <= len;) {

           if (i >= sLen)
               return operator + len - j;
           if (j >= tLen)
               return operator + len - i;

           if (sChars[i] != tChars[j]) {

               if (j + 1 < tLen && sChars[i] == tChars[j + 1]) {
                   source = addChar(source, i, tChars[j]);
                   i++;
                   j += 2;
               } else if (i + 1 < sLen && sChars[i + 1] == tChars[j]) {
                   source = deteleChar(source, i);
                   i += 2;
                   j++;
               } else {
                   source = replaceChar(source, i, sChars[j]);
                   i++;
                   j++;
               }
               operator++;

           } else {
               i++;
               j++;
           }
       }
       return operator;
   }

   @Test
   public void testMinOperationCount() {
       assertEquals(0, minOperationCount("a", "a"));
       assertEquals(1, minOperationCount("", "a"));
       assertEquals(1, minOperationCount("a", "ab"));
       assertEquals(1, minOperationCount("ad", "ab"));
       assertEquals(1, minOperationCount("ad", "a"));
       assertEquals(2, minOperationCount("ab", "bc"));

       assertEquals(6, minOperationCount("hello, world", "hello,asdf!"));
   }

   @Test
   public void testAdd() {
       assertEquals("xabcd", addChar("abcd", 0, 'x'));
   }

   @Test
   public void testReplace() {
       assertEquals("axcd", replaceChar("abcd", 1, 'x'));
   }

   @Test
   public void testDetele() {
       assertEquals("abd", deteleChar("abcd", 2));
   }

   public String addChar(String source, int index, char c) {
       return source.substring(0, index) + c + source.substring(index);
   }

   public String replaceChar(String source, int index, char c) {
       return source.substring(0, index) + c + source.substring(index + 1);
   }

   public String deteleChar(String source, int index) {
       return source.substring(0, index) + source.substring(index + 1);
   }

}

发表于 2015-02-11 13:55:45 回复(0)

牛客人007

public static int minEdit_distance(String source, String target) {
		int cost=0;
		final int n = target.length();
		final int m = source.length();

		if (m == 0)
			return n;
		if (n == 0)
			return m;
		int[][] distance_matrix = new int[m + 1][n + 1];
		distance_matrix[0][0] = 0;
		for (int i = 0; i <= n; i++) {
			distance_matrix[0][i] = i;
		}
		for (int j = 0; j <= m; j++) {
			distance_matrix[j][0] = j;
		}
		for (int i = 1; i <= m; i++) {
			char ci = source.charAt(i - 1);
			for (int j = 1; j <= n; j++) {
				char cj = target.charAt(j - 1);
				if (ci == cj) {
					cost = 0;
				} else {
					cost = 1;
				}
				distance_matrix[i][j] = Math.min(distance_matrix[i - 1][j - 1]
						+ cost, Math.min(distance_matrix[i - 1][j] + 1,
						distance_matrix[i][j - 1] + 1));
			}
		}
		return distance_matrix[m][n];
	}

发表于 2016-11-20 12:37:26 回复(0)

selfboot

动态规划

#include <string>
using namespace std;
 
classSolution {
public:
    /**
     * 返回从源字符串到目标字符串的最小操作数
     * source: 源字符串
     * target：目标字符串
     * 返回：最小操作数
     */
    intminOperationCount(string source, string target) {
        intm=source.size();
        intn=target.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        dp[0][0] = 0;
        for(inti=1;i<=m;i++){
            dp[i][0] = dp[i-1][0] + 1;
        }
        for(intj=1;j<=n;j++){
            dp[0][j] = dp[0][j-1] + 1;
        }
        for(inti=1;i<=m;i++){
            for(intj=1;j<=n;j++){
                if(source[i-1] == target[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }
                else{
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]);
                    dp[i][j] = min(dp[i][j], dp[i][j-1]) + 1;
                }
            }
        }
        returndp[m][n];
    }
};

编辑于 2016-03-26 15:30:36 回复(0)

牛客714606443号

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
/**
* 返回从源字符串到目标字符串的最小操作数
* source: 源字符串
* target：目标字符串
* 返回：最小操作数
*/
int minOperationCount(string source, string target) {

int len1 = source.length();
int len2 = target.length();
vector<vector<int>> distance_min(len1+1,vector<int>(len2+1,0));
for(int i=1;i<len1+1;i++){
distance_min[i][0] = i;
}
for(int j=1;j<len2+1;j++){
distance_min[0][j] = j;
}
for(int i=1;i<len1+1;i++){
for(int j=1;j<len2+1;j++){
distance_min[i][j] = min(distance_min[i-1][j]+1
,distance_min[i][j-1]+1);
if (source[i-1] != target[j-1]){
distance_min[i][j] = min(distance_min[i][j]
, distance_min[i-1][j-1]+1);
}
else{
distance_min[i][j] = min(distance_min[i][j]
, distance_min[i-1][j-1]);
}
}
}

return distance_min[len1][len2];


}
};

发表于 2022-03-05 22:03:21 回复(0)

dwtfukgv

#include <string>
using namespace std;
 
class Solution {
public:
    /**
     * 返回从源字符串到目标字符串的最小操作数
     * source: 源字符串
     * target：目标字符串
     * 返回：最小操作数
     */
    int minOperationCount(string source, string target) {
        string &a = source, &b = target;
          vector<vector<int> > dp = vector<vector<int> > (a.size()+1, vector<int>(b.size()+1, 0));
          for(int i = 1; i <= a.size(); ++i)  dp[i][0] = i;
          for(int i = 1; i <= b.size(); ++i)  dp[0][i] = i;
          for(int i = 1; i <= a.size(); ++i)
            for(int j = 1; j <= b.size(); ++j){
              if(a[i-1] == b[j-1])  dp[i][j] = dp[i-1][j-1];
              else   dp[i][j] = min(dp[i][j-1], min(dp[i-1][j-1], dp[i-1][j])) + 1;
            }
          return dp[a.size()][b.size()];
    }
};

发表于 2019-08-11 19:33:38 回复(0)

蓝枫灬

今天头条面上这道题了，凉凉

发表于 2019-04-25 15:09:05 回复(0)

落地卡布奇诺

http://www.doc88.com/p-9532775574400.html 清晰

编辑于 2018-07-22 22:57:12 回复(0)

王雄飞

超时

发表于 2015-08-14 23:10:17 回复(1)

HoldOn

#include <string>
using namespace std;

class Solution {
public:
/**
* 返回从源字符串到目标字符串的最小操作数
* source: 源字符串
* target：目标字符串
* 返回：最小操作数
*/
int minOperationCount(string source, string target) {
            int slen = source.size();
    int tlen = target.size();
    const char* s = source.c_str();
    const char* t = target.c_str();
    int a[200][200];
    for (int j = 0; j<=slen; j++)
        a[0][j] = j;
    for (int i = 1; i<=tlen; i++)
        a[i][0] = i;

    for (int i = 1; i<=tlen; i++)
        for (int j = 1; j<=slen; j++){
            if (t[tlen-i] == s[slen-j])
                a[i][j] = a[i - 1][j - 1];
            else{
                a[i][j] = min(min(a[i - 1][j - 1], a[i - 1][j]), a[i][j - 1]) + 1;
            }

        }

    return a[tlen][slen];
}
};

发表于 2015-06-28 18:31:46 回复(0)

JackBurd

public int min(int a, int b, int c){
        if(a < b){
            return a < c ? a : c;
        }else{
            return b < c ? b : c;
        }
    }

public int getMinDis(String s1, String s2){
        int n1 = s1.length();
        int n2 = s2.length();
        
        int f[][] = new int [n1+1][n2+1];
        
        for(int i = 1; i <= n1; i ++){
            f[i][0] = i;
        }
        
        for(int i = 1; i <= n2; i ++){
            f[0][i] = i;
        }
        
        for(int i = 1; i <= n1; i ++){
            for(int j = 1; j <= n2; j ++){
                if(s1.charAt(i-1) == s2.charAt(j-1)){
                    f[i][j] = f[i-1][j-1];
                }else{
                    f[i][j] = min(f[i-1][j-1], f[i][j-1], f[i-1][j]) + 1;
                }
            }
        }
        
        return f[n1][n2];
    }

发表于 2015-05-01 21:34:00 回复(0)