WUSTOJ 1889: 編輯距離（Java）

轉自：?LintCode：119.編輯距離(動态規劃) - HxxxxxxU的部落格 - CSDN部落格

題目連結：?1889: 編輯距離

分析?

名詞解釋
A				// 字元串A
B				// 字元串B
minOperateNum	// 最少操作次數
t1, t2, t3		// 臨時變量
           

• A

  和

  B

  長度都為 ，顯然

  minOperateNum[0][0] = 0

  。

• A

  長度為 ，

  B

  長度為

  1

  ，顯然隻需要在

  A

  末尾插入一個字元（即

  B

  末尾的字元），

  minOperateNum[0][1] = 1

  。

• A

  長度為

  1

  ，

  B

  長度為 ，顯然隻需要将

  A

  末尾字元删除即可。

  minOperateNum[1][0] = 1

  。

• A = "c"

  ，

  B = "c"

  ，去掉末尾相同字元，則

  A

  和

  B

  長度都為 ，故

  minOperateNum[1][1] = minOperateNum[0][0]

  。

• A = "c"

  ，

  B = "d"

  ，将

  c

  替換成

  d

  使得末尾字元相同，去掉末尾相同字元，那麼

  A

  和

  B

  長度為 ，故

  minOperateNum[1][1] = minOperateNum[0][0] + 1

  。

• A

  長度為 ，

  B = "cd"

  ，在

  A

  末尾插入

  c

  和

  d

  使得

  A

  和

  B

  末尾字元相同，去掉相同字元，

  A

  和

  B

  長度為 ，故

  minOperateNum[0][2] = 2

  。

• A = "d"

  ，

  B = "cd"

  ，末尾字元相同，去掉，

  A

  長度為 ，

  B = "c"

  ，故

  minOperateNum[1][2] = minOperate[0][1] = 1

  。

• A = "c"

  ，

  B = "cd"

  ，末尾字元不同
  • 在

    A

    末尾插入

    d

    使得

    A = "cd"

    和

    B = "cd"

    相同，故

    t1 = minOperateNum[1][1] = minOperateNum[0][0] = 0

    。
  • 将

    A

    末尾的字元

    c

    删除使得

    A

    長度為 ，故

    t2 = minOperateNum[0][2] = 2

    。
  • 将

    A

    末尾的

    c

    替換成

    B

    末尾的字元

    d

    ，那麼

    A = "d"

    ，末尾字元相同去掉，故

    t3 = minOperateNum[0][1] = 1

    。
  • 上述三種操次數最少為

    t1 = 0

    加上本身的一次操作，故

    minOperateNum[1][2] = t1 + 1 = 1

    。

輸入資料如下：

sfdqxbw
gfdgw
           

對應的最少操作次數對照表如?

最少操作次數對照表

A\B	1（g）	2（gf）	3（gfd）	4（gfdg）	5（gfdgw）
1	2	3	4	5
1（s）	1	1	2	3	4	5
2（sf）	2	2	1	2	3	4
3（sfd）	3	3	2	1	2	3
4（sfdq）	4	4	3	2	2	3
5（sfdqx）	5	5	4	3	3	3
6（sfdqxb）	6	6	5	4	4	4
7（sfdqxbw）	7	7	6	5	5	4

代碼?

/**
 * Time 435ms
 * @author wowpH
 * @version 2.2
 * @date 2019年5月24日下午11:52:41
 * Environment:	Windows 10
 * IDE Version:	Eclipse 2019-3
 * JDK Version:	JDK1.8.0_112
 */

import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
	private static int minOperate(String a, String b) {
		// 最少操作的次數
		int[][] minOperateNum = new int[a.length() + 1][b.length() + 1];
		// 字元串B長度為0時，字元串A隻需要删除自身的全部字元即可
		for (int i = 1; i <= a.length(); i++) {
			minOperateNum[i][0] = i;
		}
		// 字元串A長度為0時，字元串A隻需要插入字元串B的全部字元即可
		for (int i = 1; i <= b.length(); i++) {
			minOperateNum[0][i] = i;
		}
		int t1, t2, t3;// 臨時變量
		for (int i = 1; i <= a.length(); i++) {
			for (int j = 1; j <= b.length(); j++) {
				if (a.charAt(i - 1) == b.charAt(j - 1)) {// 末尾字元相同
					minOperateNum[i][j] = minOperateNum[i - 1][j - 1];
				} else {// 末尾字元不同
					// 在字元串A末尾插入一個【字元串B末尾的】字元使得AB末尾字元相同
					t1 = minOperateNum[i][j - 1];
					// 将字元串A末尾的字元删除
					t2 = minOperateNum[i - 1][j];
					// 将字元串A末尾的字元替換成字元串B末尾的字元使得AB末尾字元相同
					t3 = minOperateNum[i - 1][j - 1];
					// 取種操作中次數最少的一種操作加1即為目前的最少操作次數
					minOperateNum[i][j] = Math.min(t3, Math.min(t1, t2)) + 1;
				}
			}
		}
		// 傳回目前最少操作次數，即為結果
		return minOperateNum[a.length()][b.length()];
	}

	public static void main(String[] args) {
		String a, b;
		Scanner sc = new Scanner(new InputStreamReader(System.in));
		while (sc.hasNext()) {
			a = sc.next();
			b = sc.next();
			System.out.println(minOperate(a, b));
		}
		sc.close();
	}
}
           

版權聲明：

1. 轉載請于首頁注明連結形式的WUSTOJ 1889: 編輯距離（Java）——wowpH；
2. 代碼原創，公開引用不能删除首行注釋（作者，版本号，時間等資訊）；
3. 如果有疑問歡迎評論區留言，盡量解答；
4. 如果有錯誤，還望大俠評論區指正。