leetcode522. 最长特殊序列 II(java)

题目描述

难度 - 中等
leetcode522. 最长特殊序列 II

给定字符串列表 strs ，返回其中 最长的特殊序列 的长度。如果最长特殊序列不存在，返回 -1 。
特殊序列 定义如下：该序列为某字符串 独有的子序列（即不能是其他字符串的子序列）。
s 的 子序列可以通过删去字符串 s 中的某些字符实现。
例如，“abc” 是 “aebdc” 的子序列，因为您可以删除"aebdc"中的下划线字符来得到 “abc” 。“aebdc"的子序列还包括"aebdc”、 “aeb” 和 “” (空字符串)。

示例 1：
输入: strs = [“aba”,“cdc”,“eae”]
输出: 3

示例 2:
输入: strs = [“aaa”,“aaa”,“aa”]
输出: -1

提示:
2 <= strs.length <= 50
1 <= strs[i].length <= 10
strs[i] 只包含小写英文字母

枚举法

首先要搞明白，这道题是要干嘛的，题目很难理解，通俗点解释就是。
给出一个字符串数组，在里面找出字符串满足当前字符串不是字符串数组中其他字符串的子序列，返回满足条件的字符串中 最长的字符串的长度

看懂题目应该就不难了，其实就是比较一个字符串，是不是其他字符串的字串，找出所有满足条件的，然后取最长的做答案。
那么我们就需要两个循环，不断拿一个字符串和其他字符串去对比。对比时呢，可以用双指针的方式去判断。
即初始时指针 pti 和 ptj 分别指向两个字符串的首字符。如果两个字符相同，那么两个指针都往右移动一个位置，表示匹配成功；否则只往右移动指针 ptj，表示匹配失败。如果 pti​ 遍历完了整个字符串，就说明 str[i]是 str[j] 的子序列。
在所有满足要求的 str[i]中，我们选出最长的那个，返回其长度作为答案。如果不存在满足要求的字符串，那么返回 −1。

代码演示

  public int findLUSlength(String[] strs) {
          int ans = -1;
          int n = strs.length;
          for(int i = 0; i < n;i++){
              boolean check = true;
              for(int j = 0; j < n;j++){
                  if(i != j && check(strs[i],strs[j])){
                      check = false;
                      break;
                  }
              }
              if(check){
                  ans = Math.max(ans,strs[i].length());
              }
          }
          return ans;
      }

    public boolean check(String s,String t){
        int sIndex = 0;
        int tIndex = 0;
        while(sIndex < s.length() && tIndex < t.length()){
            if(s.charAt(sIndex) == t.charAt(tIndex)){
                sIndex++;
            }
            tIndex++;
        }
        return sIndex == s.length();
    }


    public boolean isSubseq(String s, String t) {
        int ptS = 0, ptT = 0;
        while (ptS < s.length() && ptT < t.length()) {
            if (s.charAt(ptS) == t.charAt(ptT)) {
                ++ptS;
            }
            ++ptT;
        }
        return ptS == s.length();
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42