我要招人

去企业版

首页 > 试题广场 >

最长特殊子序列（一）

[编程题]最长特殊子序列（一）

热度指数：1245 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个由小写英文字母组成的的字符串 s 和 t ，请返回这两个字符串的最长特殊子序列的长度。

特殊子序列的定义是：某个字符串的某一个子序列（不一定连续），无法在另一个字符串中找到同样的子序列则称为特殊子序列。

如果没有特殊子序列，则输出-1。

数据范围： $1 \le len(s),len(t) \le 10^5 \$ ，两个字符串都由小写英文字母组成

示例1

输入

"nowcoder","nowcoder"

输出

-1

示例2

输入

"nowcoder","nawcoder"

输出

算法知识视频讲解

在努力存钱的外卷侠很胆小

class Solution:

def longestUniqueSubsequence(self, s: str, t: str) -> int:

# write code here

if s==t:

return -1

else:

return max(len(s),len(t))

发表于 2024-12-19 22:13:00 回复(0)

Python3

fy659

首先,我们需要理解什么是"最长特殊子序列"。根据定义,它是存在于一个字符串中,但不存在于另一个字符串中的最长子序列。

现在,让我们考虑给定的两个字符串 s 和 t 的可能情况: a) 如果 s 和 t 完全相同(就像示例中的情况),那么不存在特殊子序列,因为任何存在于 s 中的子序列也必然存在于 t 中。这种情况下,我们应该返回 -1。 b) 如果 s 和 t 不同,那么较长的那个字符串本身就是一个特殊子序列,因为它不可能是另一个较短字符串的子序列。

基于以上分析,我们可以得出一个简单的算法:

如果 s 和 t 相同,返回 -1
否则,返回 s 和 t 中较长的那个的长度

发表于 2024-10-09 10:42:12 回复(0)

C++

一品统合

两个字符串一致，返回-1。

两个字符串不一致，返回其中较长的一个的长度。

class Solution {
public:
    int longestUniqueSubsequence(string s, string t) {
        if (s == t) {
            return -1;
        } else {
            return max(s.length(), t.length());
        }
    }
};

发表于 2023-05-14 23:24:48 回复(0)

小谷围做题家

package main
//import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @param t string字符串 
 * @return int整型
*/
func longestUniqueSubsequence( s string ,  t string ) int {
    if s==t{
        return -1
    }
    return max(len(s),len(t))
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

发表于 2023-03-10 23:54:02 回复(0)

猪猪侠新新酱

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @param t string字符串 
 * @return int整型
 */
int longestUniqueSubsequence(char* s, char* t ) {
    // write code here
    if(strcmp(s,t)==0)
       return -1;
    else{
        return strlen(s)>strlen(t)?strlen(s):strlen(t);
    }
}

发表于 2023-01-08 15:20:02 回复(0)

Python2

菜鸡升职记

# -*- coding: utf-8 -*-

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串
# @param t string字符串
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/1009ff84764b4640845be677f6faab3e?tpId=196&tqId=40560&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    算法：
        1. 两字符串长度不同时，我们选择较长的字符串作为最长特殊子序列，显然它不会是较短字符串的子序列。
        2. 两字符串长度相同时：
            如果相等，说明任选其一，都是另外一个的子序列，返回 -1
            否则，任选一个都不能成为另一个的子序列
    复杂度：
        时间复杂度：O(n)
        空间复杂度：O(1)
    """

    def longestUniqueSubsequence(self, s, t):
        # write code here
        if s == t:
            return -1
        return max(len(s), len(t))


if __name__ == "__main__":
    sol = Solution()

    # s, t = "nowcoder", "nowcoder"

    # s, t = "nowcoder", "nawcoder"

    s, t = "abc", "abbc"

    res = sol.longestUniqueSubsequence(s, t)

    print res

发表于 2022-07-07 14:58:10 回复(0)

Java

唐喻铭

俩字符串相等，必然返回-1

不相等，返回长度较长的字符串的长度

import java.util.*;

public class Solution {
    public int longestUniqueSubsequence (String s, String t) {
        if(!s.equals(t))
            return s.length()>t.length()?s.length():t.length();
        return -1;
    }
}

发表于 2022-05-28 14:12:58 回复(0)

danspace

class Solution:
    def longestUniqueSubsequence(self , s: str, t: str) -> int:
        # write code here
        c = max(len(s), len(t))
        for i in range(c):
            if s[i] != t[i]:
                return c
        return -1

发表于 2022-04-24 09:15:10 回复(0)

Javascript

ZoeNull

/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @param t string字符串
* @return int整型
*/
function longestUniqueSubsequence( s , t ) {
// write code here
var c = Math.max(s.length,t.length)
for(let i = 0 ; i < c ; i++){
if(s[i] != t[i]){
return c
}
}
return -1
}
module.exports = {
longestUniqueSubsequence : longestUniqueSubsequence
};

发表于 2022-04-22 20:22:26 回复(0)