3112、访问消失节点的最小时间

题目

给你两个字符串 a 和 b，请返回 这两个字符串中 最长的特殊序列 的长度。如果不存在，则返回 -1 。

「最长特殊序列」 定义如下：该序列为 某字符串独有的最长
子序列
（即不能是其他字符串的子序列） 。

字符串 s 的子序列是在从 s 中删除任意数量的字符后可以获得的字符串。

例如，”abc” 是 “aebdc” 的子序列，因为删除 “aebdc” 中斜体加粗的字符可以得到 “abc” 。 “aebdc” 的子序列还包括 “aebdc” 、 “aeb” 和 “” (空字符串)。

示例 1：

输入: a = "aba", b = "cdc"
输出: 3
解释: 最长特殊序列可为 "aba" (或 "cdc")，两者均为自身的子序列且不是对方的子序列。

示例 2：

输入：a = "aaa", b = "bbb"
输出：3
解释: 最长特殊序列是 "aaa" 和 "bbb" 。

示例 3：

输入：a = "aaa", b = "aaa"
输出：-1
解释: 字符串 a 的每个子序列也是字符串 b 的每个子序列。同样，字符串 b 的每个子序列也是字符串 a 的子序列。

提示：

• 1 <= a.length, b.length <= 100
• a 和 b 由小写英文字母组成

分析

• 要么相等，返回-1；
• 要么找出长度最长的字符串，返回其长度。

代码

class Solution {
    public int findLUSlength(String a, String b) {
        if (a.equals(b)) {
            return -1;
        } else {
            int ans = Math.max(a.length(), b.length());
            return ans;
        }

    }
}

题目

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

分析

需要针对长度最长进行枚举：

• 长度小雨当前已知的最长字符串，继续循环
• 二次枚举，发现当前字符串不是特殊串，继续从头循环
• 更新特殊字符串的长度

代码实现

class Solution {
    public int findLUSlength(String[] strs) {
        int ans = -1;
        next:
        for (int i = 0; i < strs.length; i++) {
            if (strs[i].length() <= ans) { // 不会让 ans 变大
                continue;
            }
            // 二次枚举，判断strs[i]是否是字符串数组中某个字符串的子串
            for (int j = 0; j < strs.length; j++) {
                if (j != i && isSubseq(strs[i], strs[j])) {
                    continue next;// 这里从头循环没问题，因为ans已经
                }
            }
            ans = strs[i].length();
        }
        return ans;
    }

    // 判断 s 是否为 t 的子序列
    private boolean isSubseq(String s, String t) {
        int i = 0;
        for (char c : t.toCharArray()) {
            if (s.charAt(i) == c && ++i == s.length()) { // 所有字符匹配完毕
                return true; // s 是 t 的子序列
            }
        }
        return false;
    }
    
}

// 不用next段
class Solution {
    public int findLUSlength(String[] strs) {
        int ans = -1;
        // next:
        for (int i = 0; i < strs.length; i++) {
            if (strs[i].length() <= ans) { // 不会让 ans 变大
                continue;
            }
            // 二次枚举，判断是否需要跳过strs[i]的长度更新
            boolean needContinue = false;
            for (int j = 0; j < strs.length; j++) {
                if (j != i && isSubseq(strs[i], strs[j])) {
                    needContinue = true;
                    continue;
                }
            }
            if (!needContinue) {
                ans = strs[i].length();
            }
        }
        return ans;
    }

    // 判断 s 是否为 t 的子序列
    private boolean isSubseq(String s, String t) {
        int i = 0;
        for (char c : t.toCharArray()) {
            if (s.charAt(i) == c && ++i == s.length()) { // 所有字符匹配完毕
                return true; // s 是 t 的子序列
            }
        }
        return false;
    }
}

排序 + 贪心

class Solution {
    public int findLUSlength(String[] strs) {
        // 排序，用于找到目标值，立即返回
        Arrays.sort(strs, (a, b) -> b.length() - a.length());
        next:
        for (int i = 0; i < strs.length; i++) {
            for (int j = 0; j < strs.length; j++) {
                if (j != i && isSubseq(strs[i], strs[j])) {
                    continue next;
                }
            }
            return strs[i].length();// 找到了一个，肯定时最大的
        }
        return -1;
    }

    // 返回 s 是否为 t 的子序列
    private boolean isSubseq(String s, String t) {
        int i = 0;
        for (char c : t.toCharArray()) {
            if (s.charAt(i) == c && ++i == s.length()) { // 所有字符匹配完毕
                return true; // s 是 t 的子序列
            }
        }
        return false;
    }
}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com