LeetCode 🟢 521. Longest Uncommon Subsequence I

🔗 🟢 521. Longest Uncommon Subsequence I

tags: 字串(String) 腦筋急轉彎(Brain Teaser)

題意

給定兩個字串 $a$ 和 $b$，請返回在 $a$ 和 $b$ 之間 最長的不同子序列 的長度。如果不存在不同子序列，則返回 $-1$。

若一個子序列恰好是 $a$ 或 $b$ 其中一個字串的子序列，且不是另一個字串的子序列，則稱為 不同子序列。

思路：腦筋急轉彎(Brain Teaser)

這道題是一道腦筋急轉彎的問題。我們需要注意的是，如果兩個字串 $a$ 和 $b$ 是相同的，則 $a$ 的任何子序列都會是 $b$ 的子序列，反之亦然。

因此，如果 $a$ 和 $b$ 是相同的，則它們之間不會有任何不同的子序列，所以答案應該是 $-1$。反之，如果 $a$ 和 $b$ 不同，那麼它們自身就是最長的不同子序列，故取兩者中較長的長度即可。

複雜度分析

• 時間複雜度：$\mathcal{O}(\min (n, m))$，其中 $n$ 和 $m$ 分別為字串 $a$ 和 $b$ 的長度。
• 空間複雜度：$\mathcal{O}(1)$。

PythonC++

class Solution:
    def findLUSlength(self, a: str, b: str) -> int:
        return max(len(a), len(b)) if a != b else -1

class Solution {
public:
    int findLUSlength(string a, string b) {
        return a != b ? max(a.size(), b.size()) : -1;
    }
};

---

寫在最後

Cover photo is generated by @たろたろ, thanks for their work!