Система проверки сайта не принимает решение, пожалуйста подскажите где ошибка.
Собственно задача:
1002.Телефонные номера
Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
В современном мире вы встречаетесь с огромным количеством телефонных номеров, которые со временем становятся всё длиннее и длиннее. И вам приходится запоминать эти номера. Одним из простых способов запоминания является сопоставление букв каждой цифре, как показано на следующем рисунке:
1 ij 2 abc 3 def
4 gh 5 kl 6 mn
7 prs 8 tuv 9 wxy
0 oqz
Таким образом, каждому слову или группе слов может быть сопоставлен уникальный номер, так что можно запоминать слова вместо телефонных номеров. Очевидно, есть особый шарм в том, чтобы найти простую взаимосвязь между словом, используемым для запоминания телефонного номера, и владельцем этого номера. Так, телефонный номер 941837296 вашего друга, играющего в шахматы, может быть прочитан как WHITEPAWN (белая пешка), а номер 2855304 Вашего любимого учителя может быть прочитан как BULLDOG (бульдог).
Напишите программу, находящую самую короткую последовательность слов (имеющую наименьшее количество слов), которая соответствует заданному номеру телефона и заданному списку слов. Соответствие описано на рисунке выше.
Исходные данные
Ввод состоит из набора тестов. Первая строка каждого теста содержит номер телефона, к которому нужно подобрать мнемонику. Номер состоит не более чем из 100 цифр. Вторая строка содержит общее количество слов в словаре (максимум 50 000). Каждая из оставшихся строк содержит одно слово, состоящее не более чем из 50 строчных латинских букв. Общий размер ввода не превосходит 300 килобайт. Последняя строка ввода содержит число −1.
Результат
Каждая строка вывода должна содержать кратчайшую последовательность слов, найденную вашей программой.
Слова должны быть разделены одиночными пробелами. Если для входных данных нет решения, соответствующая
строка вывода должна содержать текст No solution.
.
Если существует несколько решений, имеющих одинаковое количество слов, можете выбрать любое из них.
Ввод и вывод данные авторами для примера:
7325189087
5
it
your
reality
real
our
4294967296
5
it
your
reality
real
our
-1
# Ожидаемый результат
reality our
No solution.
Мои вводные для теста:
2272583262772
11
ba
ra
ku
k
ss
u
ma
da
m
a
ssa
-1
По логике ответ должен быть
ba ra ku da ma ssa
Но это решение почему-то в список возможных не попадает.
Причем если ma
расположить после da
то это решение находится.
Вот список решений из которых идет выбор оптимального:
['ba', 'ra', 'ku', 'da', 'm', 'a', 'ss', 'a']
['a', 'a', 'ra', 'ku', 'da', 'm', 'a', 'ss', 'a']
И соответственно оптимальным код считает:
ba ra ku da m a ss a
Ну и соответственно валидатор не принимает это решение.
Подскажите пожалуйста где косяк
Мое решение:
keyboard = {'1': 'ij', '2': 'abc', '3': 'def',
'4': 'gh', '5': 'kl', '6': 'mn',
'7': 'prs', '8': 'tuv', '9': 'wxy',
'0': 'oqz'}
while True:
phone_num = input()
solutions = []
if phone_num == '-1':
break
phone_len = len(phone_num)
words = [input() for _ in range(int(input()))]
collector = []
for word in words:
if len(word) > phone_len:
continue
solution = []
for i in range(len(word)):
if word[i] not in keyboard[phone_num[i]]:
break
else:
solution.append(word)
test_solution = []
while test_solution != solution:
test_solution = solution.copy()
raw_solution = ''.join(solution)
len_solution = len(raw_solution)
new_words = [item for item in words if len(item) <= phone_len - len_solution]
if new_words:
for item in new_words:
raw_solution = ''.join(solution)
len_solution = len(raw_solution)
test_string = raw_solution + item
len_test_string = len(test_string)
if len_test_string > phone_len:
continue
for s in range(len_solution, len_test_string):
if test_string[s] not in keyboard[phone_num[s]]:
break
else:
solution.append(item)
solutions.append(solution)
if solutions:
solutions.sort(key=lambda g: len(g))
print(*solutions[0])
else:
print('No solution.')
i adgk
но боюсь что, если-бы оптимальное решение было длиннее то оно не попало-бы туда['reality', 'ityour', 'your', 'real', 'ouq', 'it']
, то правильной комбинацией будутreal ityour
, у вас же он выдаст толькоreality
как правильный ответ