522. 最長特殊序列 II : 經典 LCS 運用題

題目描述

這是 LeetCode 上的 522. 最長特殊序列 II ，難度為 中等。

Tag : 「LCS」、「最長公共子序列」、「序列 DP」、「枚舉」、「動态規劃」

給定字元串清單 ​

​strs​

​​，傳回其中 最長的特殊序列 。如果最長特殊序列不存在，傳回

特殊序列 定義如下：該序列為某字元串 獨有的子序列（即不能是其他字元串的子序列）。

​

​s​

​​ 的 子序列可以通過删去字元串 ​

​s​

​ 中的某些字元實作。

• 例如，​

  ​"abc"​

  ​​ 是​

  ​"aebdc"​

  ​​ 的子序列，因為您可以删除​

  ​"aebdc"​

  ​​ 中的下劃線字元來得到​

  ​"abc"​

  ​​ 。​

  ​"aebdc"​

  ​​ 的子序列還包括​

  ​"aebdc"​

  ​​、​

  ​"aeb"​

  ​​ 和​

  ​""​

  ​ (空字元串)。

示例 1：

輸入: strs = ["aba","cdc","eae"]

輸出: 3      

示例 2:

輸入: strs = ["aaa","aaa","aa"]

輸出: -1      

提示:

• ​

  ​strs[i]​

  ​ 隻包含小寫英文字母

LCS

記 ​

​strs​

​​ 數組長度為 ，單個 的最大長度 。其中 資料範圍為 ， 資料範圍為 。

根據題意，我們可以枚舉每個 ，檢查其是否為其他 的子序列，這需要枚舉所有點對，複雜度為 。同時記錄周遊過程中的最大長度 ​​

​ans​

​​，用于剪枝（對于字元串長度本身小于等于 ​

​ans​

​​ 的

我們可以實作一個 ​

​check​

​​ 函數來檢查 ​

​s1​

​​ 是否為 ​

​s2​

​​ 的子序列，該問題可轉化為求 ​

​s1​

​​ 和 ​

​s2​

​​ 的最長公共子序列長度。若最長公共子序列長度為 ​

​s1​

​​ 長度，說明 ​

​s1​

​​ 為 ​

​s2​

​​ 的子序列，此時 不滿足條件，否則我們使用 的長度來更新 ​​

​ans​

​​。​

​check​

​​ 函數的複雜度為 。

不了解 LCS 的同學可以看前置 🧀 : ​​LCS 模闆題​​

是以總的計算量為 ，可以過。

代碼：

class Solution{
    public int findLUSlength(String[] strs){
        int n = strs.length, ans = -1;
        for (int i = 0; i < n; i++) {
            if (strs[i].length() <= ans) continue;
            boolean ok = true;
            for (int j = 0; j < n && ok; j++) {
                if (i == j) continue;
                if (check(strs[i], strs[j])) ok = false;
            }
            if (ok) ans = strs[i].length();
        }
        return ans;
    }
    boolean check(String s1, String s2){
        int n = s1.length(), m = s2.length();
        if (m < n) return false;
        int[][] f = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                f[i][j] = s1.charAt(i - 1) == s2.charAt(j - 1) ? f[i - 1][j - 1] + 1 : f[i - 1][j - 1];
                f[i][j] = Math.max(f[i][j], f[i - 1][j]);
                f[i][j] = Math.max(f[i][j], f[i][j - 1]);
                if (f[i][j] == n) return true;
            }
        }
        return false;
    }
}      

• 時間複雜度：檢查每個是否符合要求，需要枚舉所有的點對，複雜度為；求解 LCS 問題的複雜度為。整體複雜度為
• 空間複雜度：

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.522​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。

為了友善各位同學能夠電腦上進行調試和送出代碼，我建立了相關的倉庫：github.com/SharingSour… 。