最长特殊子序列（二）

# -*- 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