Поиск слова минимальной длины в заданной строке
Вот постановка задачи с платформы кодирования:
Учитывая строку S (которая может содержать несколько слов), вам нужно найти слово минимальной длины. Примечание. Если несколько слов имеют одинаковую длину, ответом будет первое слово минимальной длины в строке. Слова разделяются только одним пробелом. Ограничения: 1 <= Длина строки S <= 10^5
Я знаю эффективное решение, но это то, что я попробовал в своей первой попытке -
string = input().strip()
n=len(string)
words=string.split()
dic = {}
for word in words:
dic[word]=len(word)
word = ""
if n!=0:
mini = len(words[0])
word=words[0]
for wordss in dic:
if (dic[wordss]<mini):
word = wordss
mini = dic[wordss]
print(word)
Проблема в том, что он проходит только 2 из 5 тестовых случаев, которые скрыты (мне недоступны). Я не совсем уверен в проблеме этого подхода. Какие крайние случаи я упускаю?
Какую версию Python вы используете? Одной из проблем может быть порядок итерации словаря. Начиная с Python 3.7, это гарантированный порядок вставки. Если порядок итерации не является порядком вставки, не гарантируется, что вы вернете первое слово минимальной длины.
Это не говорит вам, почему тестовые примеры провалились, верно? Это может быть просто TLE, если оценщик очень строгий. Хеширование занимает некоторое время.
Чтобы решить эту проблему, вам не нужно разбивать строку. Просто перебирайте строку, находя расстояние между последовательными пробелами.
ваше решение не работает в случае, когда строка очень длинная, 10 ^ 5 - очень длинная строка, и ваше решение просто неэффективно и достигает ограничения по времени выполнения.
Не отмечайте это как dsa. Тег dsa предназначен для Digital Signature Algorithm.
Спасибо за материалы. Вероятно, это TLE (возможно, мне придется проверить версию Python, которую они использовали).
Ответы 2
когда вы повторяете dic в python, он не возвращает ключи и значения в том же порядке, в котором вы добавляете ключ и значения в dic. так например: строка = книга, он, она, кто ключ возврата из вашего кода может быть do, он или она но правильный ответ - первый с минимальной длиной.
На самом деле этот ответ неверен/отсутствует важная информация. Порядок итерации гарантированно является порядком вставки для Python 3.7+. Кроме того, второе предложение не имеет особого смысла. Пожалуйста, обновите свой ответ.
Зачем вообще заморачиваться со словарем? Вы можете просто найти минимум по ходу дела.
string = input().strip()
minlen = len( string ) + 1
bestword = ""
for word in string.split():
L = len( word )
if L < minlen:
minlen = L
bestword = word
print( bestword )
Пример:
Three blind mice see how they run
see
Спасибо. Мне известны эффективные решения этой проблемы, но я не был уверен, почему получаю ошибки при использовании словаря для этой проблемы. Я использовал два списка: один для хранения слов, а другой для хранения их длины. Использование min() и index() вернуло мне первое слово минимальной длины.
Какова цель словаря
dic? Его элементы могут быть не упорядочены по вставке в старых версиях Python, не так ли?