кодесурса
«Python

Python: Найти наименьшее окно, которое содержит все символы данной строки

script1adsense2code
script1adsense3code

Строка 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 программирования


script1adsense4code
script1adsense5code
disqus2code
script1adsense6code
script1adsense7code
script1adsense8code
buysellads2code