通用解法原理：

令 N 为电话号码的长度。

我们将字典表示为 M 个单词的列表。

所有字典单词都可以立即重写为数字序列。

然后我们创建一个维度为 N+1 x N+1 的方阵（我假设所有地方的索引都从 0 开始）。

矩阵的每个单元格 (i,j) = k 意味着我们有一个字典中编号为 k 的单词，它与电话数字的 i .. j-1 部分匹配。

用值 -1 填充其所有单元格。这将意味着我们没有这样的词。

然后，在所有单词的循环中，我们检查它们适合电话号码的哪一部分并填写矩阵。

然后，广度优先搜索在我们的矩阵中找到从 0 到 N 的路径。

如果找到路径，则路径的单元格值下的字典中的单词将是问题的解决方案，否则“无解决方案”。

矩阵填充时间 O(NxM)。广度优先搜索时间 O(NxN)。

不是最好的方法：

n = len(phone_num)
m = int(input())
words = [input() for _ in range(m)]

# Создаём матрицу (n+1) x (n+1)
a = [[-1] * (n+1) for i in range(n+1)]


wordNumbers = [convertToNumber(words[i]) for i in range(m)]

# Заполняем матрицу переходов
# перебираем слова и проверяем, что они совпадают с частью номера телефона
for i in range(n):
    for k in range(m):
        number = wordNumbers[k]
        number_length = len(number)

        if (phone_num[i:i+number_length] == number):
            a[i][i+number_length]=k


#Поиск в ширину

# Сюда будем записывать вершины пути 
# (вес, откуда пришли, куда идём)
# По вершине на каждую цифру номера
vertex = [(10000000,-1,-1)] * (n+1)

stack = []
stack.append(0)
vertex[0]=(0, 0, 0)

while(stack):
    top = stack.pop()
    ver = vertex[top]
    new_weight = ver[0] + 1
    for j in range(top+1, n+1):
        k = a[top][j]
        if k > -1:
            v = vertex[j]
            if v[0]>new_weight:
                if v[1] == -1:
                    stack.append(j)
                vertex[j] = (new_weight, top, k)


# Извлечение пути

rver = vertex[n]
if rver[1] == -1: #Мы не достигли конца
    print('No solution.')
else:
    way = []
    pos = n
    while pos != 0:
        v = vertex[pos]
        way.insert(0,words[v[2]])
        pos = v[1]
    print(' '.join(way))

其余的你可能明白。

另一种解决方案。通过所有测试。

# Класс, описывающий структуру вершин графа
class Vertex(object):
    def __init__(self, value, predecessor):
        # Слово
        self.value = value
        # Список вершин-наследников = вершина предка + длина слова
        self.successor = predecessor + len(value)
        # Метка посещения вершины
        self.is_explored = False

    def __eq__(self, other):
        return self.successor == other.successor


# Функция перевода слова в его цифровое представление
def get_number(value):
    letters = {
        'i': '1', 'j': '1', 'a': '2', 'b': '2', 'c': '2', 'd': '3', 'e': '3', 'f': '3', 'g': '4', 'h': '4', 'k': '5',
        'l': '5', 'm': '6', 'n': '6', 'p': '7', 'r': '7', 's': '7', 't': '8', 'u': '8', 'v': '8', 'w': '9', 'x': '9',
        'y': '9', 'o': '0', 'q': '0', 'z': '0'
    }
    return ''.join([letters[ch] for ch in value])


# Возвращает список всех возможных вершин слова
def get_vertex(edge, path):
    start = 0
    while True:
        try:
            vertex = path.index(edge, start)
            yield (vertex)
            start = vertex + 1
        except ValueError:
            break


# Функция нахождения кратчайшего пути методом поиска в глубину (BFS)
def bfs_shortest_path(graph, start, goal):
    queue = [[vertex] for vertex in graph[start]]

    while queue:
        path = queue.pop(0)
        node = path[-1]
        if node.is_explored:
            continue
        try:
            neighbours = graph[node.successor]
            for neighbour in neighbours:
                new_path = list(path)
                new_path.append(neighbour)
                queue.append(new_path)
                if neighbour.successor == goal:
                    return new_path
        except KeyError:
            pass

        node.is_explored = True

    return None


if __name__ == '__main__':
    while True:
        phone = input()
        if phone == '-1':
            break

        # Метка существования слова, с которого начинается номер
        is_start = False
        # Метка существования возможного результата
        is_result = False
        result = ''
        # Граф
        dictionary = {}

        for _ in range(int(input())):
            word = input()
            if is_result:
                continue
            number = get_number(word)
            if number == phone:
                is_result = True
                result = word
            else:
                for position in get_vertex(number, phone):
                    if position == 0:
                        is_start = True
                    vertex_word = Vertex(word, position)
                    try:
                        if any(map(lambda w: w == vertex_word, dictionary[position])):
                            continue
                        dictionary[position] += [vertex_word]
                    except KeyError:
                        dictionary[position] = [vertex_word]

        if is_result:
            print(result)
            continue
        if is_start:
            result = bfs_shortest_path(dictionary, 0, len(phone))
            if result:
                print(' '.join([word.value for word in result]))
                continue
            print('No solution.')
        else:
            print('No solution.')