一道華為的筆試題，講一下思路？

01-16

給出兩個字元串A,B。將A字元串轉化為B字元串，轉化共兩種方式：刪除連續的n個字元，一次操作費用為2。增加連續的n個字元（增加的什麼由你決定），一次操作的費用為n+2。求把A變為B最小費用。
輸入：第一行輸入一個正整數（1&<=T&<=10）,表示有T組測試數據。
對於每組測試數據：
兩行字元串A,B(字元串長度不超過2000，字元僅包含小寫字母。)

輸出：對於每組測試數據，輸出一行一個整數，表示最小費用。
樣例輸入
2
dsafsadfadf
fdfd
aaaaaaaa
bbbbbbbb
樣例輸出：

7
12

經典的編輯距離的一個變種，動態規劃問題，2000^3也差不多可以過，子問題是把前m個字元變成第二個字元串的前k個字元。略微優化一下也可以到2000^2，子問題是：前m個字元變成前k個字元，且：第一個字元串末位被刪除/未被刪除；第二個字元串末位是新添加/不是新添加，合計四種子狀態。

=====================================================================

第二種方法稍微寫的具體一點：

F[m,n,k] - 將A[0:m]變成B[0:n]，且：

k = 1或3時，A[m-1]被刪除；否則A[m-1]被匹配到某個B中的字元
k = 2或3時，B[m-1]被添加到字元串；否則B[m-1]匹配到某個A中的字元

F[m,n,k]有以下方法得到：

F[0,0,0] = 0, F[0,0,k] = +∞ (k != 0), F[m, n, k] = +∞ （m &< 0或n &< 0）
k = 0：僅當A[m-1] == B[n-1]時，F[m,n,0] = min(F[m-1, n-1, 0], F[m-1, n-1, 1], F[m-1, n-1, 2], F[m-1, n-1, 2])，否則F[m,n,0] = +∞
k = 1：如果A[m-2]也被刪除，刪除A[m-1]可以合併到前一個刪除中，沒有額外費用；否則要收取費用2，所以F[m, n, 1] = min(F[m-1, n, 1], F[m-1, n, 0] + 2)
k = 2：如果B[m-2]也是新增的，添加B[m-1]可以合併到前一個添加中，費用為1；否則費用為3，所以F[m, n, 2] = min(F[m, n-1, 2] + 1, F[m, n-1, 0] + 3)
k = 3：參考3和4的情況，F[m, n, 3] = min(F[m-1, n, 3], F[m-1, n, 2] + 2, F[m, n-1, 3] + 1, F[m, n-1, 1] + 3)

最終結果為min(F[M, N, 0], F[M, N, 1], F[M, N, 2], F[M, N, 3])。考慮到其中一種簡單的方法是完全刪除A然後完全添加B，費用為N + 4，而費用單調遞增，+∞可以用N + 5來代替。

寫成Python大概就是這樣吧

def min_dist(a, b): M = len(a) N = len(b) inf = N + 5 prev, next = [None] * (N + 1), [None] * (N + 1) prev[0] = (0, inf, inf, inf) for i in range(1, N + 1): prev[i] = (inf, inf, i + 2, inf) for i in range(1, M + 1): next[0] = (2, inf, inf, inf) for j in range(1, N + 1): next[j] = (min(prev[j-1]) if a[i-1] == b[j-1] else inf, min(prev[j][1], prev[j][0] + 2), min(next[j-1][2] + 1, next[j-1][0] + 3), min(prev[j][3], prev[j][2] + 2, next[j-1][3] + 1, next[j-1][1] + 3)) prev, next = next, prev return min(prev[N])

DP/最短路均可解。如果不知道怎麼寫O(N^2)的DP優化，很簡單啊，把問題轉成最短路上SPFA即可。

以數對(I, J)視為節點，表達A串到第I位前的部分與B串J位前部分匹配所需的最小修改距離。顯然NM個點，2NM條邊的圖。根據SPFA的迭代情況，也就近似平方級了。

F(n, m): min cost to make A[0, n] to B[0, m].

if A[n] == B[m], F(n, m) = Math.min(F(n-1, m-1), Q(n, m));

Q(n, m) is the condition where we want to add/delete to the end of A. two branches,

1. Delete: Min(F(0, m),...,F(n-1, m))+2;

2. Insert: Min(F(n,0)+m,...,F(n, m-1)+1)+2;

if A[n] != B[m], F(n, m) = Q(n,m).

For base condition like F(0, m) or F(n, 0), u should know that.....

以下是我原創的不含代碼的思路。據此實測通過了華為的測試。正式考試時請不要作弊。嚴禁轉載

/** * @author: Kaiwen Sun * A qualified programmer should never ignore warnings. * Warning 警告: * If you are doing Huawei"s Online Assessment right now, please stop reading. * 如果你現在正在做華為的在線測試，請停止閱讀本文。 * Come back again after you finish the test. Don"t cheat. * 請在完成了測試之後再繼續閱讀本文。不要作弊。 * * Idea: Dynamic programming * Time complexity: O(MN), i.e. product of two strings" lengths. * Space complexity: O(MN), i.e. product of two strings" lengths. * (Update: space complexity can be O(1). Think about how, or ask in the comment zone.) * * Explanation: * dp[k][m][n] stands for the minimum cost to change length-m prefix of str1 to length-n prefix of str2. * the meaning of k is as shwon in the following table: * ------------------------------------------------------ * |not delete tail|delete tail | * |of str1 prefix |of str1 prefix | * ------------------------------------------------------ * not append tail | | | * of str2 prefix | k=0 | k=1 | * ------------------------------------------------------ * append tail | | | * of str2 prefix | k=2 | k=3 | * ------------------------------------------------------ * 這個表格是DP的四種cases的關鍵，在知乎上可能字元表格顯示得亂了，在此用文字重述一遍： * k=0: 既不刪除str1結尾，也不添加str2結尾 * k=1: 刪除str1結尾，但不添加str2結尾 * k=2: 不刪除str1結尾，但添加str2結尾 * k=3: 既刪除str1結尾，也添加str2結尾 * * Initialization (base case): * According to the meaning of dp[k][m][n] we have the following rules. inf means impossible. * * dp[0][0][0] = 0; dp[1 or 2 or 3][0][0] = inf * * dp[0][m!=0][0] = inf; dp[0][0][n!=0] = inf * * dp[1][m!=0][0] = 2; dp[1][0][n!=0] = inf * * dp[2][m!=0][0] = inf; dp[2][0][n!=0] = n+2 * * dp[3][m!=0][0] = inf; dp[3][0][n!=0] = inf * * Induction rules: * * dp[0][m][n] = min{dp[0~3][m-1][n-1]} if str1[m-1]==str2[n-1]. inf otehrwise. * * dp[1][m][n] = min{dp[0][m-1][n]+2,dp[1][m-1][n]} * * dp[2][m][n] = min{dp[0][m][n-1]+3,dp[2][m][n-1]+1} * * dp[3][m][n] = min{dp[0][m-1][n-1]+2+3,dp[1][m-1][n-1]+0+3, dp[2][m-1][n-1]+2+1, dp[3][m-1][n-1]+0+1} * * Output: * min{dp[1~4][str1.length][str2.length]} */

更新，評論很快就給出反例了，慚愧，學藝不精。不過，在華為機試的時候，這種思維對得分比較管用，平時還是要多加苦練哈。

以下是原答案

換一個思路，最大費用是n+4，也就是全部刪掉然後增加一個和B一樣的字元串。

那麼，有什麼情況可以少於n+4 呢？

第一，保留首部或者尾部相同的字元串，你只要吧剩餘部分刪掉，再增加就可以了。

第二，中間的相同字元串，由於要保留中間的字元串，需要做兩次刪除，兩次新增，也就是，除非相同的字元串足夠多，不然還不如全刪除。至少需要6個相同字元。所以，找到連續相同大於6個字元串的地方，保留下來，其他的全刪了，應該就可以了。

不知道有誰能舉出不知道有沒有相反的例子？

具體演算法是，

從A開始，找到大於6的相同字元串，接著，往後找，保留刪除即可。如果不放心，可以把A的所有子串都找一遍，選個費用最小的子串。

主要思路就是，沒有六個相同的字元串，直接刪然後增加。否則，再說。

華為的題，動態規劃能寫出來的同學比較少，這種思路，至少能得一些分，有些情況可能漏掉了，或者結果不對，沒關係，只對一部分測試用例也是有分的。有時候，來不及寫規劃，吧特殊的用例處理好也不錯啊，比如，你直接返回n+4，不也能得一些分？

利息相關，前華為實習生，在內部oj有1多分。

工程問題，如果可以窮舉，最好用窮舉歸類，這樣進度可控，出錯概率小，可維護，任務劃分也比較清楚。有感而發。

今天剛好刷到這道題，總共兩種變種，可以用DP完成。

Edit DistanceDelete Operation for Two Strings

希望對你有幫助

= .=基本贊同匿名用戶和 @靈劍的思路..

按naive的DP來做, 結尾應該只有三種情況即(不修改,刪除結尾,添加結尾).

匿名用戶沒考慮結尾不同對費用產生的影響不一樣的情況.

DP的思路大概就是分別考慮三種情況,

1. 不修改, 只有當A[i]==b[j]的情況才可能存在, 此時費用等於將A[0:i-1]變換為B[0:j-1]的最小費用,否則為INF

2. 添加結尾, 考慮添加的長度為k,此時費用為將A[0:i]變換成B[0:j-k]再加上一個根據結尾不同變換的COST1

3. 刪除結尾, 考慮刪除的長度為k,此時費用為將A[0:i-k]變換為B[0:j]再加上一個根據結尾不同變換的COST2

然後再補充一些A為空串和B為空串的特殊情況即可..

附代碼:

#define _CRT_SECURE_NO_WARNINGS #include& #include& #include& #include& #define INF 3000 using namespace std; int de[2010][2010], ae[2010][2010], ne[2010][2010]; char s1[2010], s2[2010]; int main() { //freopen("io/in.txt", "r", stdin);freopen("io/out.txt", "w", stdout); int n, l1, l2; char c; scanf("%d%c", n, c); while (n--) { char* tmp = s1; char c; while ((scanf("%c", c) != EOF) c != " ")*(tmp++) = c; *tmp = ""; tmp = s2; while ((scanf("%c", c) != EOF) c != " ")*(tmp++) = c; *tmp = ""; l1 = strlen(s1); l2 = strlen(s2); for (int i = 0; i &<= l1; i++) { de[0][i] = 2; ae[0][i] = ne[0][i] = INF; } for (int i = 0; i &<= l2; i++) { ae[i][0] = i + 2; de[i][0] = ne[i][0] = INF; } ne[0][0] = 0; for (int j = 1; j &<= l2; j++) for (int i = 1; i &<= l1; i++) { ne[j][i] = s1[i - 1] == s2[j - 1] ? min(min(ne[j-1][i-1], ae[j-1][i-1]), de[j-1][i-1]) : INF; ae[j][i] = de[j][i] = INF; for (int k = 1; k &<= j; k++) ae[j][i] = min(ae[j][i], min(ae[j - k][i] + k, min(de[j - k][i] + k + 2, ne[j - k][i] + k + 2))); for (int k = 1; k &<= i; k++) de[j][i] = min(de[j][i], min(de[j][i - k], min(ae[j][i - k] + 2, ne[j][i - k] + 2))); } printf("%d ", min(min(ne[l2][l1], ae[l2][l1]), de[l2][l1])); } return 0; }

樣例:

輸出:

時間複雜度N^3, N^2的代碼什麼時候想起來再補吧= .=

應該是dp，但沒懂第一組樣例是怎麼變過去的