Определите, отличаются ли две строки не более чем на n символов - PullRequest
Новая
       27

Определите, отличаются ли две строки не более чем на n символов

2 голосов
/ 08 июля 2020

Я пытаюсь понять, как подойти к этому вопросу.

Учитывая список строк (los), строку s и целое число, привязанное к n, функция должна выдать True, если все строки в los находятся не более чем на n символов от s, в противном случае - False.

Например, 

Input: (["ccat","hpat","ppat"], "ppat", 2)

Output: True

и для случая False 

Input: (["ccat","hpat","that"], "ppat", 1)

Output: False

Спасибо!

Ответы [ 3 ]

3 голосов
/ 08 июля 2020

Часть вашего решения называется «расстояние Левенштейна». Подробнее здесь

Вы можете либо реализовать самостоятельно, либо найти python решение здесь

после реализации этого вы может индивидуально проверить расстояние, если оно находится в пределах N, с помощью al oop

1 голос
/ 08 июля 2020

Как вы пояснили, вы хотите найти разницу между двумя строками по символам с их позициями , вы можете сделать следующее:

  • Перебирать список один за другим.
  • Для каждого слова в списке сравните его с предоставленным строковым символом за символом.
  • Если символ из одного не совпадает с другим, увеличьте счетчик различий.
  • Если разница становится больше необходимой разницы, вернуть False, иначе вернуть True.
  • Имейте в виду, что две сравниваемые строки могут иметь разную длину. Учитывайте это при их расчете.

Фрагмент: 

def isSame(str_list,s,diff_offset):
    s_len = len(s)
    for each_s in str_list:
        diff = abs(len(each_s) - s_len) # initialize with difference of string length
        length = min(len(each_s),s_len)
        for i in range(0,length):
            if s[i] != each_s[i]:
                diff = diff + 1
            if diff > diff_offset:
                return False # if difference is more than required, then return false
    return True


print(isSame(["ccat","hpat","ppat"], "ppat", 2))
print(isSame(["ccat","hpat","ppatru"], "ppat", 2))
print(isSame(["ccat","hpat","that"], "ppat", 1))

Обновление:

Как согласно формулировке задачи, если длины не совпадают, просто верните False перед началом сравнения строк char по char. 

def isSame(str_list,s,diff_offset):
    s_len = len(s)
    for each_s in str_list:
        if len(each_s) != s_len:
            return False
        diff = 0
        for i in range(0,s_len):
            if s[i] != each_s[i]:
                diff = diff + 1
            if diff > diff_offset:
                return False # if difference is more than required, then return false
    return True


print(isSame(["ccat","hpat","ppat"], "ppat", 2))
print(isSame(["ccat","hpat","ppatru"], "ppat", 2))
print(isSame(["ccat","hpat","that"], "ppat", 1))
0 голосов
/ 08 июля 2020

Я бы использовал расстояние Левенштейна , чтобы решить эту проблему. в модуле Левенштейна есть функция с именем «distance»: 

from Levenshtein import distance

функция получает 2 строки и возвращает расстояние между ними. это то, что вы ищете.

, тогда я бы применил его ко всем элементам списка (понимание, l oop et c ..) и проверил, все ли верно.

...