【LeetCode】522. Longest Uncommon Subsequence II 解题报告(Python)

时间:2021-07-24 08:28:18

【LeetCode】522. Longest Uncommon Subsequence II 解题报告(Python)

标签(空格分隔): LeetCode

作者: 负雪明烛
id: fuxuemingzhu
个人博客: http://fuxuemingzhu.cn/


题目地址:https://leetcode.com/problems/longest-uncommon-subsequence-ii/description/

题目描述:

Given a list of strings, you need to find the longest uncommon subsequence among them. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings.

A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string.

The input will be a list of strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn’t exist, return -1.

Example 1:

Input: "aba", "cdc", "eae"
Output: 3

Note:

  1. All the given strings’ lengths will not exceed 10.
  2. The length of the given list will be in the range of [2, 50].

题目大意

找出最长非公共子序列。公共子序列的定义是一个字符串可由另一个字符串删除某些字符得到。如果在一组字符串中,某一个字符串不是任何另外的字符串的公共子序列,那么这就是它是全组的非公共子序列。找出最长的长度。

解题方法

做题多了,没想到暴力解法就能过了。

写出公共子序列的判断函数。主要是两个位置pos和i,如果能找到子字符串中的某个位置,那么就把全字符串的位置后移。

寻找最长非公共子序列的时候直接两重for循环即可,不要想太复杂。

代码如下:

class Solution(object):
def findLUSlength(self, strs):
"""
:type strs: List[str]
:rtype: int
"""
longest = -1
_len = len(strs)
for i in range(_len):
issub = False
for j in range(_len):
if i == j:
continue
if self.checkSubString(strs[i], strs[j]):
issub = True
break
if not issub:
longest = max(longest, len(strs[i]))
return longest def checkSubString(self, substr, string):
if len(substr) > len(string): return False
if substr == string: return True
if not substr: return True
pos = 0
for i in range(len(string)):
if pos == len(substr):
break
if substr[pos] == string[i]:
pos += 1
return pos == len(substr)

参考资料:

  1. http://www.cnblogs.com/grandyang/p/6680548.html
  2. https://blog.csdn.net/zsensei/article/details/75227927

日期

2018 年 8 月 27 日 ———— 就要开学了!

【LeetCode】522. Longest Uncommon Subsequence II 解题报告(Python)的更多相关文章

  1. LeetCode 521 Longest Uncommon Subsequence I 解题报告

    题目要求 Given a group of two strings, you need to find the longest uncommon subsequence of this group o ...

  2. 【LeetCode】521. Longest Uncommon Subsequence I 解题报告(Python)

    作者: 负雪明烛 id: fuxuemingzhu 个人博客: http://fuxuemingzhu.cn/ 目录 题目描述 题目大意 解题方法 日期 题目地址:https://leetcode.c ...

  3. 522. Longest Uncommon Subsequence II

    Given a list of strings, you need to find the longest uncommon subsequence among them. The longest u ...

  4. 【leetcode】522. Longest Uncommon Subsequence II

    题目如下: 解题思路:因为given list长度最多是50,我的解法就比较随意了,直接用一个嵌套的循环,判断数组中每个元素是否是其他的subsequence,最后找出不属于任何元素subsequen ...

  5. 522 Longest Uncommon Subsequence II 最长特殊序列 II

    详见:https://leetcode.com/problems/longest-uncommon-subsequence-ii/description/ C++: 方法一: class Soluti ...

  6. 【LeetCode】Pascal's Triangle II 解题报告

    [LeetCode]Pascal's Triangle II 解题报告 标签(空格分隔): LeetCode 题目地址:https://leetcode.com/problems/pascals-tr ...

  7. 【LeetCode】731. My Calendar II 解题报告(Python)

    [LeetCode]731. My Calendar II 解题报告(Python) 作者: 负雪明烛 id: fuxuemingzhu 个人博客: http://fuxuemingzhu.cn/ 题 ...

  8. 【LeetCode】137. Single Number II 解题报告(Python)

    [LeetCode]137. Single Number II 解题报告(Python) 标签: LeetCode 题目地址:https://leetcode.com/problems/single- ...

  9. 【LeetCode】227. Basic Calculator II 解题报告(Python)

    [LeetCode]227. Basic Calculator II 解题报告(Python) 标签(空格分隔): LeetCode 作者: 负雪明烛 id: fuxuemingzhu 个人博客: h ...

随机推荐

  1. stopping NetworkManager daemon failed

    1 初次安装NetworkManager时发现,无法将这个服务关闭 2 上网找了一圈,也没找到原因 3 重启服务器后就能正常关闭了 4 将该服务删除重装也能正常关闭 5 下回重装系统时再观察一下

  2. Orchard源码--初步(1)

    1.打开解决方案Orachard.sln 2.直接启动项目调试 3.接着你会看到下图 呵呵,有点啰嗦( ̄︶ ̄)↗ 涨 4.点击上图的‘Finish Setup’后

  3. HTC Vive开发笔记之手柄控制

    怎么安装设备,配置环境我就不说了,自行百度,教程很多也很简单.接下来说下Vive手柄的控制. 手柄是HTC Vive的重要交互手段,我们通过第一个图片应该对其有一个直观的了解了,总共是九个按钮: 第一 ...

  4. reactjs 入门

    地址搜集:http://www.cocoachina.com/webapp/20150604/12035.html class 属性需要写成 className ,for 属性需要写成 htmlFor ...

  5. dnsever 邮件记录

    记录,备忘

  6. POJ1182 食物链(并查集)

    食物链 Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 55260   Accepted: 16210 Description ...

  7. HTml <meta>标签的使用(重要)

    <meta> 元素可提供有关页面的元信息(meta-information),比如针对搜索引擎和更新频度的描述和关键词. 1.设置网页字符编码 <meta http-equiv=&q ...

  8. PADS封装

    CAE 是原理图符号DECAL 是PCB封装PART 是将 CAE和 DECAL结合映射起来.比如PART包含了CAE和DECAL的管腿对应关系.CAE的1号腿,不一定对应DECAL的1号腿的.Pin ...

  9. 搭建ftp服务器实现文件共享

    FTP服务器(File Transfer Protocol Server)是在互联网上提供文件存储和访问服务的计算机,它们依照FTP协议提供服务. FTP(File Transfer Protocol ...

  10. 201521123004 《Java程序设计》第7周学习总结

    1. 本周学习总结 以你喜欢的方式(思维导图或其他)归纳总结集合相关内容. 2. 书面作业 ArrayList代码分析 1.1 解释ArrayList的contains源代码 答:从ArrayList ...