Python: Найти наименьшее окно, которое содержит все символы данной строки
Строка Python: упражнение-75 с решением
Напишите программу на Python, чтобы найти наименьшее окно, которое содержит все символы данной строки.
Пример решения :
Код Python:
from collections import defaultdict
def find_sub_string(str):
str_len = len(str)
# Count all distinct characters.
dist_count_char = len(set([x for x in str]))
ctr, start_pos, start_pos_index, min_len = 0, 0, -1, 9999999999
curr_count = defaultdict(lambda: 0)
for i in range(str_len):
curr_count[str[i]] += 1
if curr_count[str[i]] == 1:
ctr += 1
if ctr == dist_count_char:
while curr_count[str[start_pos]] > 1:
if curr_count[str[start_pos]] > 1:
curr_count[str[start_pos]] -= 1
start_pos += 1
len_window = i - start_pos + 1
if min_len > len_window:
min_len = len_window
start_pos_index = start_pos
return str[start_pos_index: start_pos_index + min_len]
str1 ="asdaewsqgtwwsa"
print("Original Strings:\n",str1)
print("\nSmallest window that contains all characters of the said string:")
print(find_sub_string(str1))
Пример вывода:
Оригинальные строки: asdaewsqgtwwsa Самое маленькое окно, которое содержит все символы указанной строки: daewsqgt
Блок - схема:
Визуализируйте выполнение кода Python:
Следующий инструмент визуализирует, что компьютер делает шаг за шагом при выполнении указанной программы:
Редактор кода Python:
Есть другой способ решить это решение? Внесите свой код (и комментарии) через Disqus.
Предыдущий: Напишите программу на Python, чтобы найти минимальное окно в данной строке, которое будет содержать все символы другой данной строки.
Далее: Напишите программу на Python для подсчета количества подстрок из заданной строки строчных алфавитов с ровно k различными (заданными) символами.
Каков уровень сложности этого упражнения?
Новый контент: Composer: менеджер зависимостей для PHP , R программирования