Pythonを使っている方は、OR-Toolsという数理最適化ライブラリを使うことで巡回セールスマン問題(TSP)の近似解を求めることができます。
ノードの数が多いとTLEしますが、今回のように200程度ならそれなりの経路を制限時間内に提示してくれます。

1. 単語ごとの最小コストを計算しました(DPでできます)。開始位置や終了位置は固定せずに、純粋に5文字を打刻するのに必要な最小コストおよびその際の経路を計算しました。
2. 各単語間を移動する際のコストを計算しました。各単語の開始位置と終了位置は1.の処理で決定済みのため計算できます。
3. OR-Toolsに2.で計算したコストを流し込んでTSPをしました。

OR-Toolsの使い方はドキュメントにサンプルコード付きで書いてあるので、コピペすれば少し変更を加えるだけで使えると思います。
https://developers.google.com/optimization/routing/tsp?hl=ja

なお、PyPyではModuleNotFoundErrorが出るのでCPythonを使うといいです。
TSP部分のコードは以下の通りです。

def create_data_model():
    """Stores the data for the problem."""
    data = {}
    data["distance_matrix"] = cost_between_words
    data["num_vehicles"] = 1
    data["depot"] = 0
    return data

data = create_data_model()
manager = pywrapcp.RoutingIndexManager(
    len(data["distance_matrix"]), data["num_vehicles"], data["depot"]
)
routing = pywrapcp.RoutingModel(manager)

def distance_callback(from_index, to_index):
    """Returns the distance between the two nodes."""
    # Convert from routing variable Index to distance matrix NodeIndex.
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return data["distance_matrix"][from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(distance_callback)

routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
)

search_parameters.local_search_metaheuristic = (
    routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.seconds = 1
search_parameters.log_search = False

def print_solution(manager, routing, solution):
    route_global = []
    index = routing.Start(0)
    while not routing.IsEnd(index):
        route_global.append(manager.IndexToNode(index))
        index = solution.Value(routing.NextVar(index))
    route_global = route_global[1:]
    route_global = [r-1 for r in route_global]
    return route_global
    
solution = routing.SolveWithParameters(search_parameters)
if solution:
    route_global = print_solution(manager, routing, solution)