最长特殊子序列（二）

# -*- 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();
    }
}