Определите количество цепочек длины 4, где все четыре символа различны
Скачайте текстовый файл, состоящий не более чем из 106 символов A, B, C и D. Определите количество цепочек длины 4, где все четыре символа различны. Не очень понимаю как проверять сразу длину цепочки и количество символов, идея была примерно такая:
file = open("24.14.txt")
line = file.readline()
count = 0
maxx_summ = 0
for i in range(len(line)-1):
if line[i] != line[i+1] and line[i+1] != line[i+2] and line[i+2] != line[i+3]:
count += 1
maxx_summ = max(maxx_summ,count)
else:
count = 1
print(maxx_summ)
Ответы (5 шт):
Опираясь на комментарий выше, вот такой код бы получился.
with open("24.14.txt") as file:
line = file.readline()
count = 0
for i in range(0, len(line), 4):
current_piece = line[i:i + 4]
if len(set(current_piece)) == 4:
count += 1
print(count)
Берем срезы по 4 символа, делаем из среза множество (структура данных, где все элементы уникальны). Если длина множества равна 4, значит в срезе было 4 разных символа и его нужно посчитать.
ты внутри цикла используешь
line[i],line[i+1],line[i+2],line[i+3]Следовательно тебе нужно убедиться, чтоi + 3не превышаетlen(line) - 1. Получается нужно уменьшить длину цикла доlen(line) - 3Для того, чтобы проверить, что у тебя все символы различны, можно использовать set
{line[i], line[i+1], line[i+1], line[i+3]}и проверить, что количество элементов в этом сете равна 4У тебя счетчики
countиmaxx_summиспользуются примерно для одного и того же, можно обойтись одним
в итоге, если модифицировать твой код, получится
count = 0
for i in range(len(line)-3):
if len({line[i], line[i+1], line[i+2], line[i+3]}) == 4:
count += 1
print(count)
Если кому интересно решение которое я придумал, без исправлений, правда с точки зрения нормально программиста оно ужасно):
file = open("24.14.txt")
line = file.readline()
count = 0
maxx_summ = 0
for i in range(len(line)-4):
if (line[i] != line[i+1] and line[i] != line[i+2]
and line[i] != line[i+3]) and (line[i+1] != line[i+2] and line[i+1] != line[i+3]) and (line[i+2] != line[i+3]):
count += 1
print(count)
рефакторинг... рефакторинг...
#with open("24.14.txt") as file:
#line = file.readline().strip()
line = '123456'
count = sum(len(set(line[i:i + 4])) == 4 for i in range(len(line)-3))
print(count)
>>>3
Благодаря мистеру @Spatz, обратим внимание на то, что при чтении строки из файла, к ней будет добавлен '\n'. Поэтому необходимо обработать строку strip() - это удалит в конце строки '\n'.
Справка по strip().
Извлекаем из строки все возможные куски длины k, превращаем их в множество, размер множества сравниваем с k, если равенство, увеличиваем счётчик:
def count_set_substrings(s, k):
count = 0
for i in range(len(s) - k + 1):
if len(set(s[i:i + k])) == k:
count += 1
return count
Тоже самое но в более питоническом стиле:
def count_set_substrings(s, k):
return sum(1 for i in range(len(s) - k + 1) if len(set(s[i:i + k])) == k)
Если длина строки и длина подстроки могут быть большими, то предложенные решения не самые быстрые. Время работы пропорционально (N - K)K, где N - длина строки, K - длина проверямых подстрок. Можно сделать лучше.
Заведем словарь, в котором будем хранить символы и их количество. Первоначально словарь заполняется первыми K символами строки. Затем символы обрабатываются парами: один вставляется, один удаляется. Если размер словаря достигает K прибавляем единицу к счётчику. Пример:
строка и операции словарь со размер указатели счётчиками букв словаря |A B C D D C B A { } 0 [A]B C D D C B A +A {A: 1 } 1 [A B]C D D C B A +B {A: 1, B: 1 } 2 [A B C]D D C B A +C {A: 1, B: 1, C: 1 } 3 [A B C D]D C B A +D {A: 1, B: 1, C: 1, D: 1} 4 A[B C D D]C B A -A +D { B: 1, C: 1, D: 2} 3 A B[C D D C]B A -B +C { C: 2, D: 2} 2 A B C[D D C B]A -C +B { B: 1, C: 1, D: 2} 3 A B C D[D C B A] -D +A {A: 1, B: 1, C: 1, D: 1} 4
В каждой итерации цикла словарь обновляется за константу. Общая сложность программы будет N. От K время работы не зависит:
class Bag:
def __init__(self):
self._bag = {}
def add(self, v):
self._bag[v] = 1 + self._bag.get(v, 0)
def remove(self, v):
if self._bag[v] == 1:
del self._bag[v]
else:
self._bag[v] -= 1
def __len__(self):
return len(self._bag)
def count_set_substrings(s, k):
it1 = iter(s)
bag = Bag()
for c1 in itertools.islice(it1, k):
bag.add(c1)
count = 0
if len(bag) == k:
count += 1
it2 = iter(s)
for c1, c2 in zip(it1, it2):
bag.add(c1)
bag.remove(c2)
if len(bag) == k:
count += 1
return count