Сделать две строки похожими - PullRequest
Новая
       5

Сделать две строки похожими

0 голосов
/ 20 сентября 2019

У Рахула есть две строки str1 и str2, которые могут иметь или не иметь одинаковую длину, определяют минимальную стоимость, чтобы сделать их похожими.стоит 1 за удаление или добавление одного символа.например: если строки "abc" и "abd", строка становится "abcd" и "abdc".таким образом, ответ 2

Мой код: 

   n=int(input())
string1=[]
string2=[]
for i in range(0,n):
    string1.append(input().lower())
    string2.append(input().lower())
for i in range(0,n):
    count1=0
    count2=0
    x=sorted(list(string1[i]))
    y=sorted(list(string2[i]))
    for i in x:
        if i not in y:
            count1+=1
    for i in y:
        if i not in x:
            count2+=1
    a=count1+len(x)
    b=count2+len(y)
    if(a==b):
        print(count1+count2)
    else:
        print(count1+count2+abs(a-b))

Это работает для ввода, который я даю.Но когда я провожу его через тесты на взлом, он не проходитПожалуйста, помогите мне понять, что я делаю не так

1 Ответ

0 голосов
/ 20 сентября 2019

Я думаю, вам нужен вариант так называемого расстояния редактирования https://en.wikipedia.org/wiki/Edit_distance. Самой длинной общей подпоследовательностью (LCS) может быть решение для этого https://en.wikipedia.org/wiki/Longest_common_subsequence_problem.

...