给定两个由小写英文字母组成的的字符串 s 和 t ,请返回这两个字符串的最长特殊子序列的长度。
特殊子序列的定义是:某个字符串的某一个子序列(不一定连续),无法在另一个字符串中找到同样的子序列则称为特殊子序列。
如果没有特殊子序列,则输出-1。
数据范围: ,两个字符串都由小写英文字母组成
"nowcoder","nowcoder"
-1
"nowcoder","nawcoder"
8
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 }
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @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); } }
# -*- 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