OD 算法题 B卷【最长公共后缀】

最长公共后缀

• 查找字符串数组中的最长公共后缀，如果不存在公共后缀，则返回‘@Zero’;
• 字符串长度范围为【2, 1000】;
• 字符串中字符ascii码值为【1， 126】；

示例1
输入：
[“abc”, “bbc”, “c”]
输出：
“c”

示例2
输入：
[“aa”, “bb”, “cc”]
输出：
“@Zero”

python实现:

• 所有字符串按照长度升序排序；
• 取第一个最短的字符串，双指针截取子串，并判断是否为列表中剩余字符串的公共后缀部分；
• 取一个最长的公共子串；

def is_demand(sub_str):""" 当前子串是否在列表中的每个字符串中 """global string_listreturn all([True if s.endswith(sub_str) else False for s in string_list])string_list = eval(input())
# 按照长度排序
string_list.sort(key=lambda i: len(i))# 取第一个最短的字符串
start = string_list.pop(0)
start_len = len(start)
tgt = ""
pre = 0  # 单指针
while pre < start_len:sub_str = start[pre:]  # 公共后缀if is_demand(sub_str):tgt = sub_strbreakpre += 1if tgt:print(tgt)
else:print("@Zero")

其他方案：

• 初始化一个主动比较的字符串；
• 假如公共后缀xx存在，则 任意两个字符串的公共后缀长度一定大于等于该xx的长度；

# 解析输入的字符串为数组
string_list = input().replace("[", "").replace("]","").replace("\"", "").split(",")flag = True
# 取第一个字符串
result = string_list[0]# 遍历后续的字符串
for i in range(1, len(string_list)):length1 = len(result)length2 = len(string_list[i])j = 1# 两个字符串，比较最后一个字符while length1 >= j and length2 >= j and result[length1 - j] == string_list[i][length2 - j]:j += 1# 当前两个字符串没有公共后缀，则结束if j == 1:flag = Falsebreak# 取当前两个字符串的公共后缀result = result[length1 - j + 1:]if flag:print(result)
else:print("@Zero")