LeetCode 🟡 522. Longest Uncommon Subsequence II

🔗 🟡 522. Longest Uncommon Subsequence II

tags: 字串(String) 雙指標(Two Pointers) 排序(Sorting) 雜湊表(Hash Table)

題意

給定一個字串陣列 $\text{strs}$ ，回傳其中 最長的不同子序列 長度。如果沒有不同子序列存在，則回傳 $-1$。

在一個字串陣列中，一個不同子序列是指一個字串是其中一個字串的子序列，但不是其他字串的子序列。

字串 $s$ 的一個子序列是指從 $s$ 中刪除任意數量的字元後得到的字串。

約束條件

• $2 \leq \text{strs.length} \leq 50$
• $1 \leq \text{strs[i].length} \leq 10$
• $\text{strs[i]}$ 由小寫英文字母組成。

思路：雙指標(Two Pointers)

根據 521. Longest Uncommon Subsequence I 的結論，若一個字串的子序列是不同子序列，則該字串本身也是不同子序列，因此只要考慮所有字串中，是否有字串不是其他字串的子序列即可。

而要判斷一個字串是否為另一個字串的子序列，可以透過 雙指針(Two Pointers) 的方式來判斷，可以直接使用 392. Is Subsequence 的解法。

def isSubsequence(s: str, t: str) -> bool:
    i, j = 0, 0
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
        j += 1
    return i == len(s)

方法一：二重迴圈

最暴力的做法就是枚舉所有字串，然後遍歷所有其他字串，使用 isSubsequence 函數檢查是否為其他字串的子序列，若不是則以其長度更新答案。

複雜度分析

• 時間複雜度：$O(n^2 \cdot m)$，其中 $n$ 是 $\text{strs}$ 的長度，$m$ 是字串的最大長度。
  • 對於每個字串而言，遍歷所有其他字串，檢查是否為其他字串的子序列的時間為 $O(n \cdot m)$ 。由於需要檢查所有字串，因此總共需要 $O(n^2 \cdot m)$ 的時間。
  • 總共有 $n$ 個字串，因此總時間複雜度為 $O(n^2 \cdot m)$。
• 空間複雜度：$O(1)$。

PythonC++

class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        def isSubsequence(s: str, t: str) -> bool:
            i, j = 0, 0
            while i < len(s) and j < len(t):
                if s[i] == t[j]:
                    i += 1
                j += 1
            return i == len(s)
        ans = -1
        for i, s in enumerate(strs):
            for j, t in enumerate(strs):
                if i != j and isSubsequence(s, t):
                    break
            else:
                ans = max(ans, len(s))
        return ans

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

    bool isSubsequence(string s, string t) {
        int m = s.size(), n = t.size();
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (s[i] == t[j++]) i++;
        }
        return i == m;
    }
};

方法二：使用排序優化

基於和方法一同樣的思路，但由於我們要求的是最長的不同子序列，因此我們可以先對字串陣列 由大到小排序 ，這樣我們就可以先檢查長度最長的字串是否為其他字串的子序列，如果不是，則代表其為最長的不同子序列，直接返回其長度。

複雜度分析

• 時間複雜度：$O(n^2 \cdot m + n \log n) = O(n^2 \cdot m)$，其中 $n$ 是 $\text{strs}$ 的長度，$m$ 是字串的最大長度。
  • 排序的時間複雜度為 $O(n \log n)$。
  • 對於每個字串而言，遍歷所有其他字串，檢查是否為其他字串的子序列的時間為 $O(n \cdot m)$ 。最差情況下還是需要檢查所有字串，總共需要 $O(n^2 \cdot m)$ 的時間。
• 空間複雜度：$O(1)$ ，忽略排序所需的空間。

PythonC++

class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        def isSubsequence(s: str, t: str) -> bool:
            i, j = 0, 0
            while i < len(s) and j < len(t):
                if s[i] == t[j]:
                    i += 1
                j += 1
            return i == len(s)
        strs.sort(key=lambda x: len(x), reverse=True)
        for i, s in enumerate(strs):
            for j, t in enumerate(strs):
                if i != j and isSubsequence(s, t):
                    break
            else:
                return len(s)
        return -1

class Solution {
public:
    int findLUSlength(vector<string>& strs) {
        int n = strs.size();
        sort(strs.begin(), strs.end(), [](const string& a, const string& b) {
            return a.size() > b.size();
        });
        for (int i = 0; i < n; i++) {
            bool flag = true;
            for (int j = 0; j < n; j++) {
                if (i != j && isSubsequence(strs[i], strs[j])) {
                    flag = false;
                    break;
                }
            }
            if (flag) return strs[i].size();
        }
        return -1;
    }

    bool isSubsequence(string s, string t) {
        int m = s.size(), n = t.size();
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (s[i] == t[j++]) i++;
        }
        return i == m;
    }
};

方法三：根據出現次數優化

另一種優化方式是使用 雜湊表(Hash Table) 來計算每個字串的出現次數，由於出現次數 $> 1$ 的字串 一定不是 不同子序列，因此我們只需要考慮出現次數為 $1$ 的字串。將出現次數為 $1$ 的字串取出，並根據長度由大到小排序，對其進行判斷是否為其他字串的子序列即可。

需要注意，在判斷是否為其他字串的子序列時，仍需考慮 出現次數 $> 1$ 的字串，因為出現次數為 $1$ 的字串仍有可能是出現次數 $> 1$ 的字串的子序列。

這裡的做法是將出現次數為 $1$ 的字串保存到 $\text{uniques}$ 陣列中，然後對其進行排序，並遍歷雜湊表中的鍵值 $cnt.keys()$ ，對 $\text{uniques}$ 中的字串，判斷是否為其他字串的子序列。

複雜度分析

• 時間複雜度：$O(n^2 \cdot m)$，其中 $n$ 是 $\text{strs}$ 的長度，$m$ 是字串的最大長度。
  • 遍歷所有字串，計算出現次數需要 $O(n \cdot m)$ 的時間。
  • 對出現次數為 $1$ 的字串進行排序需要 $O(n \log n)$ 的時間。
  • 對每個出現次數為 $1$ 的字串而言，遍歷所有其他字串，檢查是否為其他字串的子序列的時間為 $O(n \cdot m)$。最差情況下還是需要檢查所有字串，總共需要 $O(n^2 \cdot m)$ 的時間。
• 空間複雜度：$O(n)$，存儲所有字串的出現次數，以及使用 $\text{uniques}$ 來存儲出現次數為 $1$ 的字串。

PythonC++

class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        def isSubsequence(s: str, t: str) -> bool:
            i, j = 0, 0
            while i < len(s) and j < len(t):
                if s[i] == t[j]:
                    i += 1
                j += 1
            return i == len(s)
        cnt = Counter(strs)
        strs = list(cnt.keys())
        uniques = [s for s, v in cnt.items() if v == 1]
        uniques.sort(key=lambda x: len(x), reverse=True)
        for s in uniques:
            for t in strs:
                if s != t and isSubsequence(s, t):
                    break
            else:
                return len(s)
        return -1

class Solution {
public:
    int findLUSlength(vector<string>& strs) {
        int n = strs.size();
        unordered_map<string, int> cnt;
        for (string& s : strs) cnt[s]++;
        vector<string> uniques;
        for (auto kv : cnt) if (kv.second == 1) uniques.push_back(kv.first);
        sort(uniques.begin(), uniques.end(), [](const string& a, const string& b) {
            return a.size() > b.size();
        });
        for (string& s : uniques) {
            bool flag = true;
            for (string& t : strs) {
                if (s != t && isSubsequence(s, t)) {
                    flag = false;
                    break;
                }
            }
            if (flag) return s.size();
        }
        return -1;
    }

    bool isSubsequence(string s, string t) {
        int m = s.size(), n = t.size();
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (s[i] == t[j++]) i++;
        }
        return i == m;
    }
};

---

寫在最後

Cover photo is generated by @ゴリラの素材屋さん, thanks for their work!

雖然時間複雜度一樣，但確實還是有一些優化的。