25 tháng 4 năm 2018 Tổng quanKhoảng cách xóa của hai chuỗi là số lượng ký tự tối thiểu bạn cần xóa trong hai chuỗi để có được cùng một chuỗi. Chẳng hạn, khoảng cách xóa giữa nhiệt và đánh là 3:
Examples: Đầu vào: Str1 = "Dog", Str2 = "Frog" Đầu ra: 3 Đầu vào: str1 = "some", str2 = "một số" đầu ra: 0 đầu vào: str1 = "some", str2 = "điều" đầu ra: 9 đầu vào: đầu vào: str1 = "", str2 = "" đầu ra: 0= "dog", str2 = "frog" output: 3 input: str1 = "some", str2 = "some" output: 0 input: str1 = "some", str2 = "thing" output: 9 input: str1 = "", str2 = "" output: 0 Constraints:
functionDeletionDistance [$ str1, $ str2] {// mã của bạn ở đây} deletionDistance[$str1, $str2] { // your code goes here } Gợi ý
Dung dịchĐặt str1len và str2len lần lượt là độ dài của str1 và str2. Hãy xem xét chức năng: Opt [i, j] trả về khoảng cách xóa cho tiền tố i'th của str1 và tiền tố thứ J của str2. Những gì chúng tôi muốn làm trong giải pháp này, là sử dụng lập trình động để xây dựng một hàm tính toán opt [str1len, str2len]. Chú ý những điều sau:
Điều này đúng vì nếu một chuỗi là chuỗi trống, chúng ta không có lựa chọn nào khác ngoài việc xóa tất cả các chữ cái trong chuỗi khác.
Điều này được giữ vì chúng ta cần xóa ít nhất một trong các chữ cái str1 [i] hoặc str2 [j] và việc xóa một trong các chữ cái được tính là 1 xóa [do đó 1 trong công thức]. Sau đó, vì chúng ta còn lại với tiền tố [i-1] 'của Str1 hoặc tiền tố [J-1]' của Str2, cần phải có mức tối thiểu giữa OPT [I-1, J] và OPT [I, J-1]. Do đó, chúng tôi có được phương trình opt [i, j] = 1 + phút [opt [i-1, j], opt [i, j-1]].
Điều này được tổ chức vì chúng tôi không cần xóa các chữ cái cuối cùng để có được cùng một chuỗi, chúng tôi chỉ cần sử dụng cùng một lần xóa mà chúng tôi sẽ làm cho các tiền tố [i-1] 'và [j-1]'. Giải pháp 1Sau khi tìm thấy các mối quan hệ trên cho OPT [I, J], chúng tôi sử dụng các phương thức lập trình động để tính toán OPT [str1len, str2len], tức là khoảng cách xóa cho hai chuỗi, bằng cách tính toán opt [i, j] cho tất cả 0 ≤ i ≤ str1len, 0 ≤ j ≤ str2len và lưu các giá trị trước đó để sử dụng sau: Pseudocode: Chức năng xóaDistance [str1, str2]: str1len = str1.length str2len = str2 đến str1len: cho j từ 0 đến str2len: nếu [i == 0]: memo [i] [j] = j other if [j == 0]: memo [i] [j] = i khác nếu [str1 [str1 [ i-1] == str2 [j-1]]: memo [i] [j] = memo [i-1] [j-1] khác: memo [i] [j] = 1 + min -1] [j], memo [i] [j-1]] return memo [str1len] [str2len] Độ phức tạp về thời gian: Chúng tôi có một vòng lặp lồng nhau thực hiện các bước O [1] ở mỗi lần lặp, do đó, chúng tôi độ phức tạp thời gian là O [N⋅m] trong đó n và m lần lượt là độ dài của str1 và str2.: we have a nested loop that executes O[1] steps at every iteration, thus we the time complexity is O[N⋅M] where N and M are the lengths of str1 and str2, respectively. Độ phức tạp của không gian: Chúng tôi lưu mọi giá trị của OPT [i, J] trong mảng 2D ghi nhớ của chúng tôi, có không gian o [n⋅m], trong đó n và m lần lượt là độ dài của str1 và str2.: we save every value of opt[i,j] in our memo 2D array, which takes O[N⋅M] space, where N and M are the lengths of str1 and str2, respectively. Giải pháp 2Giải pháp trên lấy không gian o [n⋅m] vì chúng tôi lưu tất cả các giá trị trước đó, nhưng lưu ý rằng opt [i, j] chỉ yêu cầu opt [i-1, j], opt [i, j-1] và opt [i -1, J-1]. Do đó, bằng cách lặp đầu tiên đến 0 ≤ i ≤ str1len, và sau đó cho mỗi i tính toán 0 ≤ j ≤ str2len, chúng ta chỉ cần lưu các giá trị cho I và I cuối cùng. Điều này sẽ làm giảm không gian cần thiết cho chức năng. Pseudocode: Chức năng xóaDistance [str1, str2]: # Đảm bảo chiều dài của str2 không dài hơn chiều dài của str1 nếu [str1.length Độ phức tạp về thời gian: Độ phức tạp thời gian vẫn giữ nguyên, tức là O [N⋅m], vì chúng ta vẫn chạy một vòng lặp lồng nhau với các lần lặp N⋅m.: the time complexity stays the same, i.e. O[N⋅M], since we still run a nested loop with N⋅M iterations. Độ phức tạp không gian: O [Min [N, M]], vì chúng ta chỉ cần giữ hai hàng của mảng kép.:
O[min[N,M]], as we only need to hold two rows of the double array. Mã PHP functiondeletionDistance[$str1,$str2]{$cur=range[0,strlen[$str1]];$prev=[];for[$i=0;$i deletionDistance[$str1, $str2] { $cur = range[0, strlen[$str1]]; $prev = []; for[$i=0; $i<=strlen[$str2]; $i++]{ $prev[$i] = 0; } for[$i=0; $i<strlen[$str1];$i++]{ $cur = $cur; $prev = $prev; $cur[0] = $i + 1; for[$j=0; $j<strlen[$str2];$j++]{ $sub = $str1[$i] == $str2[$j] ? 0 : 2; $cur[$j+1] = min[$prev[$j]+$sub, $cur[$j]+1, $prev[$j+1]+1]; } } return $cur[count[$cur]-1]; } Mã Python 1 [Làm việc] Defdeletiondistance [S1, S2]: Cur = List [phạm vi [Len [S2] +1]] trước = [0]*[LEN [S2] +1] . J]+1, trước [J+1] +1] returnCur [-1] deletionDistance[s1, s2]: cur = list[range[len[s2] + 1]] prev = [0] * [len[s2] + 1] for i in range[len[s1]]: cur, prev = prev, cur cur[0] = i + 1 for j in range[len[s2]]: # Substitution is same as two deletions sub = 0 if s1[i] == s2[j] else 2 cur[j+1] = min[prev[j] + sub, cur[j] + 1, prev[j+1] + 1] return cur[-1] Mã Python 2 [không hoạt động] defdeletionDistance[s1,s2]:m=[[0forjinrange[len[s2]+1]]foriinrange[len[s1]+1]]foriinrange[len[s1]+1]:forjinrange[len[s2]+1]:ifi==0:m[i][j]=sum[bytearray[s2[:j]]]elifj==0:m[i][j]=sum[bytearray[s1[:i]]]elifs1[i-1]==s2[j-1]:m[i][j]=m[i-1][j-1]else:m[i][j]=ord[s1[i-1]]+ord[s2[j-1]]+min[m[i-1][j-1],m[i-1][j],m[i][j-1]]returnm[len[s1]][len[s2]] deletionDistance[s1, s2]: m = [[0 for j in range[len[s2]+1]] for i in range[len[s1]+1]] for i in range[len[s1]+1]: for j in range[len[s2]+1]: if i == 0: m[i][j] = sum[bytearray[s2[:j]]] elif j == 0: m[i][j] = sum[bytearray[s1[:i]]] elif s1[i-1] == s2[j-1]: m[i][j] = m[i-1][j-1] else: m[i][j] = ord[s1[i-1]] + ord[s2[j-1]] + min[m[i-1][j-1], m[i-1][j], m[i][j-1]] return m[len[s1]][len[s2]] Mã Python 3 [không hoạt động] defdeletionDistance[s1,s2]:m=[[0forjinrange[len[s2]+1]]foriinrange[len[s1]+1]]foriinrange[len[s1]+1]:forjinrange[len[s2]+1]:ifi==0:m[i][j]=sum[bytearray[s2[:j]]]elifj==0:m[i][j]=sum[bytearray[s1[:i]]]elifs1[i-1]==s2[j-1]:m[i][j]=m[i-1][j-1]else:s1del=ord[s1[i-1]]s2del=ord[s2[j-1]]s1s2del=s1del+s2delm[i][j]=min[m[i-1][j-1]+s1s2del,m[i-1][j]+s1del,m[i][j-1]+s2del]returnm[len[s1]][len[s2]] deletionDistance[s1, s2]: m = [[0 for j in range[len[s2]+1]] for i in range[len[s1]+1]] for i in range[len[s1]+1]: for j in range[len[s2]+1]: if i == 0: m[i][j] = sum[bytearray[s2[:j]]] elif j == 0: m[i][j] = sum[bytearray[s1[:i]]] elif s1[i-1] == s2[j-1]: m[i][j] = m[i-1][j-1] else: s1del = ord[s1[i-1]] s2del = ord[s2[j-1]] s1s2del = s1del + s2del m[i][j] = min[m[i-1][j-1] + s1s2del, m[i-1][j] + s1del, m[i][j-1] + s2del] return m[len[s1]][len[s2]] Trường hợp kiểm traPHP $ testcase = [["", "", 0], ["", "hit", 3], ["gọn gàng", "", 4], ["Heat", "hit", 3], [" nóng "," không ", 2], [" một số "," điều ", 9], [" abc "," adbc ", 1], [" tuyệt vời "," tuyệt vời ", 0], [" ab " , "BA", 2],]; 1]]] {echo "Trường hợp kiểm tra #{$ index} không thành công \ n"; = [ ["", "", 0], ["", "hit", 3], ["neat", "", 4], ["heat", "hit",
3], ["hot", "not", 2], ["some", "thing", 9], ["abc", "adbc", 1], ["awesome", "awesome", 0],
["ab", "ba", 2], ]; foreach[$testCase as $key=>$case] { $index = $key+1; if [$case[2] !=
deletionDistance[$case[0], $case[1]]] { echo "Test case #{$index} failed Python testcase = [["", "", 0], ["", "hit", 3], ["gọn gàng", "", 4], ["nhiệt", "hit", 3], ["nóng "," không phải ", 2], [" Một số "," điều ", 9], [" ABC "," ADBC ", 1], [" Tuyệt vời "," Tuyệt vời ", 0], [" AB ", "BA", 2],];# print [testCase] index = 1; chỉ mục]+'không thành công \ n']; other: in ['#'+str [index]+'đã vượt qua = [ ["", "", 0], ["", "hit", 3], ["neat", "",
4], ["heat", "hit", 3], ["hot", "not", 2], ["some", "thing", 9], ["abc", "adbc", 1],
["awesome", "awesome", 0], ["ab", "ba", 2], ]; # print[testCase] index = 1; for case in testCase:
if[case[2] != deletionDistance[case[0], case[1]]]: print['#' + str[index] + 'failed //stackoverflow.com/questions/44490091/deletion-distance-between-2-strings //stackoverflow.com/questions/41275345/deletion-distance-between-words |
