求助佬,DFS试了十多组数据,和题解算法的答案一致,但是全部WA
查看原帖
求助佬,DFS试了十多组数据,和题解算法的答案一致,但是全部WA
1493801
manxing_楼主2024/10/4 16:59
# 解题思路                   尽管所有WA,但和别人代码结果一致
# 找最小重叠部分(minOverlap,mo)
# dfs从龙头开始深度遍历,能找到重叠部分(mo),递归遍历;找不到,更新当前龙的最大值
def is_mo(word1, word2):  # word1和word2是否有最小重叠部分,返回重叠下标
    len1 = len(word1)
    len2 = len(word2)
    num = min(len1, len2) - 1  # num为比较最小重叠部分的最多次数,-1不能存在包含关系
    for k in range(1, num + 1):
        for i in range(len1 - 1, -1, -1):
            for j in range(len2):
                if word1[len1 - k:] == word2[:k]:  # 比较是否有最小重叠部分
                    # global ind1,ind2   全局变量回溯的时候,删除的单词是等长的,ind2被覆盖了
                    # ind1=len1-k
                    ind2 = k
                    return ind2  # 重叠时word1,word2的下标
    return -1


def dfs():  # 搜索龙头和其他(包括自己)单词有最小重叠部分
    for j in range(n):
        if use[j] <= 1:
            global dragon
            if is_mo(dragon, words[j]) != -1:
                temp_str = words[j]
                index2 = is_mo(dragon, words[j])
                dragon += temp_str[index2:]  # 接龙
                use[j] += 1  # words[j]使用次数+1
                dfs()  # 搜索第j个单词是否还有龙
                use[j] -= 1  # 回溯去标号
                dragon = dragon.rstrip(temp_str[index2:])  # 回溯
    # 深度遍历到了最深一层,单词都用完,此时龙最大
    global max_len
    if len(dragon) > max_len:
        max_len = len(dragon)
    return True

n = int(input())
words = []  # 存储所有单词
dragon = ''
use = [0] * (n)  # 记录所有单词使用次数
max_len = 0  # 龙最大值
for _ in range(n):
    str1 = input()
    words.append(str1)
head = input()
for word in words:
    if head == word[0]:
        ind = words.index(word)
        use[ind] += 1
        dragon += word
        dfs()
        dragon = ''
print(max_len)

2024/10/4 16:59
加载中...