Вопрос о программировании «One Away» — распространенная проблема на собеседованиях по информатике и разработке программного обеспечения. В этой статье мы обсудим разные подходы к решению этой проблемы и приведем примеры кода на разных языках программирования. Готовитесь ли вы к собеседованию или просто интересуетесь проблемами программирования, эта статья поможет вам понять различные стратегии решения проблемы «Один в гостях».
Методы и примеры кода:
- Метод грубой силы:
Подход грубой силы включает в себя проверку каждой возможной пары строк, чтобы определить, находятся ли они «на расстоянии одной» друг от друга. Этот метод имеет временную сложность O(n^2) и не является самым эффективным решением. Тем не менее, он дает базовое понимание проблемы.
def is_one_away(str1, str2):
if abs(len(str1) - len(str2)) > 1:
return False
count = 0
for i in range(len(str1)):
if str1[i] != str2[i]:
count += 1
if count > 1:
return False
return True- Сопоставление символов.
Этот метод предполагает сравнение частот символов в двух строках. Если частоты различаются более чем на единицу, струны не находятся «на расстоянии одной» друг от друга. Временная сложность этого подхода равна O(n).
from collections import Counter
def is_one_away(str1, str2):
if abs(len(str1) - len(str2)) > 1:
return False
freq1 = Counter(str1)
freq2 = Counter(str2)
diff = sum((freq1 - freq2).values())
return diff <= 1- Скользящее окно.
Техника скользящего окна полезна при сравнении двух строк разной длины. Продвигая окно размером 2 или 3 по более длинной строке, мы можем проверить, соответствует ли подстрока более короткой строке. Временная сложность этого подхода равна O(n).
def is_one_away(str1, str2):
if abs(len(str1) - len(str2)) > 1:
return False
if len(str1) < len(str2):
str1, str2 = str2, str1
i = j = 0
diff = 0
while i < len(str1) and j < len(str2):
if str1[i] != str2[j]:
diff += 1
if diff > 1:
return False
if len(str1) == len(str2):
j += 1
else:
j += 1
i += 1
return True