给定一个长度为 n 的字符串列表,返回他们中最长的特殊子序列的长度。
特殊子序列的定义是:某个字符串的某一个子序列(不一定连续),无法在另一个字符串中找到同样的子序列则称为特殊子序列。
数据范围:, 字符串长度满足
# -*- coding: utf-8 -*- # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param strs string字符串一维数组 # @return int整型 # class Solution: """ 题目: https://www.nowcoder.com/practice/27f32e4548644ec9a8ee6251d7de30bd?tpId=196&tqId=40561&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= 算法: 对于任一字符串str[i],如果它的子序列sub是一个 特殊序列,那么在sub基础上添加一些字符得到的str[i]也是一个 特殊序列。 1. 我们使用双循环,外层循环枚举每一个字符串str[i]作为特殊序列,内层循环枚举每一个字符串str[j] (i != j),判断str[i]是否不为str[j]的子序列 2. 判断字符串s是否为字符串t的子序列: 双指针i,j分别指向s和t,从前向后遍历,当s[i] == t[j]时,同时右移;否则,右移j。直到字符串s或t边界结束,返回i == len(s) 复杂度: 时间复杂度:O(n^2 * l), n为strs的长度,l为字符串的平均长度 空间复杂度:O(1) """ def longestUniqueSubsequence(self, strs): # write code here def check(s, t): # 判断s是否为t的子序列 m, n = len(s), len(t) i, j = 0, 0 while i < m and j < n: if s[i] == t[j]: i += 1 j += 1 else: j += 1 return i == m n, res = len(strs), -1 for i in range(n): flag = False for j in range(n): if i != j and check(strs[i], strs[j]): flag = True break # 题目要求的特殊序列,对于该字符串以外的任意一个字符串来讲,都是特殊序列。反之,如果一个字符串是某一个字符串的子序列,该条件就不满足 if not flag: res = max(res, len(strs[i])) return res if __name__ == "__main__": sol = Solution() # strs = ["aba", "bbb", "eae"] strs = ["nowcoder", "nowcoderr"] res = sol.longestUniqueSubsequence(strs) print res
import java.util.*; public class Solution { public int longestUniqueSubsequence (ArrayList<String> strs) { int ret = -1; int j = 0; for(int i = 0;i < strs.size();i ++) { for(j = 0;j < strs.size();j ++) { //查看str.get(i)是否为strs中某一个字符串的子序列 if(i == j) continue; //不可以和自己比较 if(func(strs.get(i),strs.get(j))) { break; //str.get(i)是strs.get(j)的子序列 } } if(j == strs.size()) { //没有一个字符串中有str.get(i)这样的子序列 //说明该序列是特殊子序列 ret = Math.max(ret,strs.get(i).length()); } } return ret; } //查看字符串a是否是字符串b的子序列 public boolean func(String a,String b) { int j = 0; for(int i = 0;i < b.length() && j < a.length();i ++) { if(a.charAt(j) == b.charAt(i)) { j++; } } //如果j == a.length说明a中所有的字母都在b中找到了,a为b的子序列 return j == a.length(); } }