最长非公共子序列

NC205274. 最长非公共子序列

描述

Lemon 丢给你两个字母序列 $s_1$ 和 $s_2$ ，并无情地交给了你一个奇怪的任务——求最长非公共子序列。
序列 a 是 b 的子序列，当且仅当从 b 中删除一些元素（可以是零个或所有）能得到 a。
例如：
我们可以通过从 "abcde" 中删除 "b" 和 "d" 得到 "ace"，因此 "ace" 是 "abcde" 的子序列。
同理 "abcde"，"e" 和空串都是 "abcde" 的子序列；

但 "abdc" 不是 "abcde" 的子序列。

序列 c 是 $s_1$ 和 $s_2$ 的非公共子序列当且仅当它满足以下条件中的任何一个：

c 是 $s_1$ 的子序列但不是 $s_2$ 的子序列；
c 是 $s_2$ 的子序列但不是 $s_1$ 的子序列。

$s_1$ 和 $s_2$ 的非公共子序列可能有很多，你只需要求出其中长度最长的非公共子序列的长度。

输入描述

第一行包含一个字符串  ，第二行包含一个字符串 。 ()
输入保证  和  均只包含小写字母。

输出描述

在一行输出一个整数，表示最长非公共子序列的长度。
特别地，如果不存在非公共子序列，输出 -1 。

示例1

输入:

aba
abc

输出:

示例2

输入:

lemon
lemon

输出:

-1

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

pypy3(pypy3.6.1) 解法, 执行用时: 56ms, 内存消耗: 18636K, 提交时间: 2020-04-18 12:38:11

a=input()
b=input()
if(a==b):
    print(-1)
else:
    print(max(len(a),len(b)))

Python3(3.5.2) 解法, 执行用时: 28ms, 内存消耗: 3448K, 提交时间: 2020-04-18 12:12:44

s1 = input()
s2 = input()

print(max(len(s1), len(s2)) if s1 != s2 else -1)

Ruby(2.4.2) 解法, 执行用时: 51ms, 内存消耗: 7280K, 提交时间: 2020-04-18 12:49:32

a = gets.chomp
b = gets.chomp
puts a == b ? -1 : [a.size, b.size].max

上一题

下一题

详情