noip 单词接龙 python代码

### NOIP 单词接龙 Python 代码实现 对于单词接龙问题，可以采用深度优先搜索（DFS）的方法求解。为了处理这个问题，程序会构建一个图结构来表示各个单词间的连接关系，并通过递归来探索每一种可能的路径组合。 #### 构建图结构 创建邻接表形式的无向图，节点代表不同的字符串，边上的权重则对应于两个字符串之间能够共享的最大前缀/后缀长度。当遍历整个输入列表时，针对每一个字符串与其他所有字符串比较，计算它们之间的最大重叠部分并据此更新图的数据结构[^1]。 #### 记录访问状态 引入布尔类型的二维数组`used`跟踪每个单词是否已经被利用过一次或两次。这有助于防止重复使用同一个单词超过规定的次数限制[^3]。 #### 深度优先搜索算法 定义辅助函数执行实际的DFS过程，在此期间不断尝试延长当前形成的链条直到无法继续为止；与此同时维护全局变量保存最优解的信息——即最长链路及其对应的总得分。每当找到更优的结果就立即替换掉旧纪录[^2]。 以下是完整的Python代码： ```python from collections import defaultdict def max_overlap(s1, s2): """Calculate the maximum overlap between two strings.""" len_s1 = len(s1) len_s2 = len(s2) for i in range(min(len_s1, len_s2), 0, -1): if s1[-i:] == s2[:i]: return i return 0 def dfs(current_word_index, current_length, used_times, graph, words, best_solution): global longest_chain_score, longest_chain_path # Update the solution when a better one is found. if current_length > longest_chain_score: longest_chain_score = current_length longest_chain_path = list(best_solution) for next_word_index in range(len(words)): if not (next_word_index != current_word_index and sum(used_times[next_word_index]) < 2): continue new_length = current_length + len(words[next_word_index]) - graph[current_word_index][next_word_index] if new_length <= longest_chain_score: continue used_times[next_word_index].append(True) best_solution.append(next_word_index) dfs( next_word_index, new_length, used_times, graph, words, best_solution ) best_solution.pop() used_times[next_word_index].pop() if __name__ == "__main__": start_letter = input().strip() # Read starting letter from stdin. word_count = int(input()) # Number of unique words available to form chains with. words = [] for _ in range(word_count): words.append(input()) filtered_words_indices = [ idx for idx, w in enumerate(words) if w.startswith(start_letter)] # Build adjacency matrix representing overlaps among all pairs of words. graph = [[max_overlap(w1, w2) for w2 in words] for w1 in words] results = [] for initial_idx in filtered_words_indices: longest_chain_score = 0 # Initialize score tracking variables before each DFS run. longest_chain_path = [] visited_status = [[] for _ in range(len(words))] temp_result = [initial_idx] dfs(initial_idx, len(words[initial_idx]), visited_status, graph, words, temp_result) result_string = ''.join([words[i] for i in longest_chain_path]) results.append((result_string, longest_chain_score)) sorted_results = sorted(results, key=lambda item:item[1], reverse=True)[0] print(sorted_results[0]) ```