Question

522. 最长特殊序列 II

English Version

题目描述

给定字符串列表 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] 只包含小写英文字母

解法

方法一：判断子序列

判断是否独有，只需要取字符串 $s$ 本身，与其他字符串比较即可。题目可以转化为：获取非其他字符串子序列的字符串的最大长度。若不存在，返回 -1。

其中，$check(a,b)$ 用于判断字符串 $b$ 是否为字符串 $a$ 的子序列。

class Solution:
  def findLUSlength(self, strs: List[str]) -> int:
    def check(a, b):
      i = j = 0
      while i < len(a) and j < len(b):
        if a[i] == b[j]:
          j += 1
        i += 1
      return j == len(b)

    n = len(strs)
    ans = -1

    for i in range(n):
      j = 0
      while j < n:
        if i == j or not check(strs[j], strs[i]):
          j += 1
        else:
          break
      if j == n:
        ans = max(ans, len(strs[i]))
    return ans

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

  private boolean check(String a, String b) {
    int j = 0;
    for (int i = 0; i < a.length() && j < b.length(); ++i) {
      if (a.charAt(i) == b.charAt(j)) {
        ++j;
      }
    }
    return j == b.length();
  }
}

class Solution {
public:
  int findLUSlength(vector<string>& strs) {
    int ans = -1;
    for (int i = 0, j = 0, n = strs.size(); i < n; ++i) {
      for (j = 0; j < n; ++j) {
        if (i == j) continue;
        if (check(strs[j], strs[i])) break;
      }
      if (j == n) ans = max(ans, (int) strs[i].size());
    }
    return ans;
  }

  bool check(string a, string b) {
    int j = 0;
    for (int i = 0; i < a.size() && j < b.size(); ++i)
      if (a[i] == b[j]) ++j;
    return j == b.size();
  }
};

func findLUSlength(strs []string) int {
  check := func(a, b string) bool {
    j := 0
    for i := 0; i < len(a) && j < len(b); i++ {
      if a[i] == b[j] {
        j++
      }
    }
    return j == len(b)
  }

  ans := -1
  for i, j, n := 0, 0, len(strs); i < n; i++ {
    for j = 0; j < n; j++ {
      if i == j {
        continue
      }
      if check(strs[j], strs[i]) {
        break
      }
    }
    if j == n && ans < len(strs[i]) {
      ans = len(strs[i])
    }
  }
  return ans
}