cpp 解法, 执行用时: 0 ms, 内存消耗: 9.9 MB, 提交时间: 2024-06-17 09:41:28

class Solution {
    // 判断 s 是否为 t 的子序列
    bool isSubseq(string& s, string& t) {
        int i = 0;
        for (char c : t) {
            if (s[i] == c && ++i == s.length()) { // 所有字符匹配完毕
                return true; // s 是 t 的子序列
            }
        }
        return false;
    }

public:
    int findLUSlength(vector<string>& strs) {
        ranges::sort(strs, {}, [](const auto& s) { return -s.length(); });
        for (int i = 0; i < strs.size(); i++) {
            for (int j = 0; j < strs.size(); j++) {
                if (j != i && isSubseq(strs[i], strs[j])) {
                    goto next;
                }
            }
            return strs[i].length();
            next:;
        }
        return -1;
    }
};

rust 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2024-06-17 09:41:16

impl Solution {
    // 返回 s 是否为 t 的子序列
    fn is_subseq(s: &[u8], t: &str) -> bool {
        let mut i = 0;
        for c in t.bytes() {
            if s[i] == c {
                i += 1;
                if i == s.len() { // 所有字符匹配完毕
                    return true; // s 是 t 的子序列
                }
            }
        }
        false
    }

    pub fn find_lu_slength(mut strs: Vec<String>) -> i32 {
        strs.sort_unstable_by(|a, b| b.len().cmp(&a.len()));
        'next:
        for (i, s) in strs.iter().enumerate() {
            let s = s.as_bytes();
            for (j, t) in strs.iter().enumerate() {
                if j != i && Self::is_subseq(s, t) {
                    continue 'next;
                }
            }
            return s.len() as _;
        }
        -1
    }
}

javascript 解法, 执行用时: 48 ms, 内存消耗: 41.5 MB, 提交时间: 2023-03-15 09:35:51

/**
 * @param {string[]} strs
 * @return {number}
 */
var findLUSlength = function(strs) {
    const n = strs.length;
    let ans = -1;
    for (let i = 0; i < n; ++i) {
        let check = true;
        for (let j = 0; j < n; ++j) {
            if (i !== j && isSubseq(strs[i], strs[j])) {
                check = false;
                break;
            }
        }
        if (check) {
            ans = Math.max(ans, strs[i].length);
        }
    }
    return ans;
};

const isSubseq = (s, t) => {
    let ptS = 0, ptT = 0;
    while (ptS < s.length && ptT < t.length) {
        if (s[ptS] === t[ptT]) {
            ++ptS;
        }
        ++ptT;
    }
    return ptS === s.length;
}

java 解法, 执行用时: 1 ms, 内存消耗: 38.9 MB, 提交时间: 2023-03-15 09:35:28

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

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

golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-03-15 09:29:51

func isSubseq(s, t string) bool {
    ptS := 0
    for ptT := range t {
        if s[ptS] == t[ptT] {
            if ptS++; ptS == len(s) {
                return true
            }
        }
    }
    return false
}

func findLUSlength(strs []string) int {
    ans := -1
next:
    for i, s := range strs {
        for j, t := range strs {
            if i != j && isSubseq(s, t) {
                continue next
            }
        }
        if len(s) > ans {
            ans = len(s)
        }
    }
    return ans
}

python3 解法, 执行用时: 72 ms, 内存消耗: 15 MB, 提交时间: 2023-03-15 09:29:01

class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        # 双指针判断s是否t得子序列
        def is_subseq(s: str, t: str) -> bool:
            pt_s = pt_t = 0
            while pt_s < len(s) and pt_t < len(t):
                if s[pt_s] == t[pt_t]:
                    pt_s += 1
                pt_t += 1
            return pt_s == len(s)
        
        ans = -1
        # 两层循环，外层枚举每个strs[i]作为特殊子序列，
        # 内层枚举每个strs[j] (i != j )， 判断strs[i]是否为strs[j]的子序列
        for i, s in enumerate(strs):
            check = True
            for j, t in enumerate(strs):
                if i != j and is_subseq(s, t):
                    check = False
                    break
            if check:
                ans = max(ans, len(s))
        
        return ans