Практикум по строкам

Модуль про строки дал четыре набора средств, и почти любую задачу можно решить несколькими из них. Новой темы сегодня не будет — будет выбор.

Задача «сколько раз встречается буква» решается методом count — и это правильный ответ. Задача «сколько раз буква стоит рядом с такой же» методом не решается вовсе: там нужен перебор с номерами.

Практическое правило: сначала посмотрите, нет ли готового метода. Если есть — берите. Если условие требует чего-то, чего в списке методов нет, — возвращайтесь к циклу.

Сегодня темы не подписаны, и рядом стоящие задачи почти никогда не про одно и то же.

Условие: «дана строка; выведите её без символов, которые совпадают с предыдущим».

Каким средством это делается?

Ошибки модуля собраны вместе — с признаком, по которому каждая узнаётся.

Границы

1. s[i + 1] на последнем шаге цикла. Признак: string index out of range.
2. Срез на единицу короче или длиннее. Признак: ответ похож на правильный, но не тот. Сообщения нет — срез не падает.
3. s[-k:] при k = 0 даёт всю строку, а не пустую.

Неизменяемость

4. s.replace(...) без присваивания. Признак: программа выводит то, что ввели.
5. s[0] = "x" — так нельзя, строка собирается заново.

Пустое и вырожденное

6. Строка из одного символа: нет соседей, первый и последний совпадают.
7. split() на строке из пробелов даёт пустой список — цикл не выполнится ни разу.
8. Искомого нет: find вернёт −1, и это не позиция.

Коды

9. Забытый % 26 — сдвиг уезжает за z в посторонние знаки.
10. Перепутанные ord("a") и ord("A") для разных регистров.

В задачах на строки есть отдельная ловушка: решение верное, а времени не хватает.

Чаще всего виноват поиск внутри перебора. Например, «сколько различных символов в строке» через проверку каждого символа против всех предыдущих — это $n^2$ действий. На строке в сто тысяч символов получается десять миллиардов — не пройдёт.

Что делать, зависит от задачи, но два приёма закрывают почти всё:

• перебирать алфавит, а не строку. Букв всего двадцать шесть. Вместо «для каждого символа проверить остальные» — «для каждой из 26 букв посчитать, сколько раз она встречается». Это $26n$ вместо $n^2$;
• помнить предыдущее. Задачи про соседей, цепочки и повторы решаются одним проходом, если хранить один символ назад.

Прикидка та же, что в занятии 11: перемножьте длину строки на количество проходов по ней и сравните с десятью миллионами.

Лестница прежняя: пять разминочных, семь основных, три со звёздочкой. Зачёт при десяти решённых.

Подсказки в условиях остались, но они про выбор инструмента, а не про решение.

После задач — три разбора чужого кода. Все три программы выглядят правдоподобно, и все три неверны по-разному: одна ошибается на границе, вторая работает верно, но слишком долго, третья ломается на вырожденном вводе. Различать эти три случая по симптому — навык не менее полезный, чем умение писать самому.

Задача: «дана строка; выведите её последние три символа. Если символов меньше трёх, выведите всю строку».

Ученик написал:

s = input()
print(s[len(s) - 3:])

На строке abcdef программа отвечает верно — def. На строке ab она выводит ab, и это тоже верно. А на строке a выводит a — снова верно.

Ученик считает, что решение правильное. Проверьте это рассуждение: найдите вход, на котором программа ошибается, объясните причину и предложите исправление.

Задача: «дана строка из строчных латинских букв длиной до $10^5$; выведите, сколько в ней различных символов».

Ученик написал:

s = input()
count = 0

for i in range(len(s)):
    seen = False
    for j in range(i):
        if s[j] == s[i]:
            seen = True
    if not seen:
        count += 1

print(count)

На коротких примерах программа отвечает правильно, но на больших тестах получает превышение времени. Объясните, сколько примерно действий она делает, почему это не проходит, и предложите решение, которое пройдёт.

Задача: «дана строка, состоящая из слов и пробелов; выведите первое слово. Если слов нет, выведите NONE».

Ученик написал:

s = input()
parts = s.split()

if parts[0] == "":
    print("NONE")
else:
    print(parts[0])

На обычных строках программа работает. На строке из одних пробелов она завершается с ошибкой IndexError: list index out of range. Объясните, что произошло, и как проверить отсутствие слов правильно.