【綜合筆試題】難度 3/5，近期小廠面試原題

題目描述

這是 LeetCode 上的 1239. 串聯字串的最大長度 ，難度為 中等。

Tag : 「DFS」、「二進位制列舉」、「模擬退火」、「隨機化」、「啟發式搜尋」

給定一個字串陣列 arr，字串 s 是將 arr 某一子序列字串連線所得的字串，如果 s 中的每一個字元都只出現過一次，那麼它就是一個可行解。

請返回所有可行解 s 中最長長度。

示例 1： ``` 輸入：arr = ["un","iq","ue"]

輸出：4

解釋：所有可能的串聯組合是 "","un","iq","ue","uniq" 和 "ique"，最大長度為 4。 示例 2： 輸入：arr = ["cha","r","act","ers"]

輸出：6

解釋：可能的解答有 "chaers" 和 "acters"。 示例 3： 輸入：arr = ["abcdefghijklmnopqrstuvwxyz"]

輸出：26 ```

提示： * $1 <= arr.length <= 16$ * $1 <= arr[i].length <= 26$ * arr[i] 中只含有小寫英文字母

基本分析

根據題意，可以將本題看做一類特殊的「數獨問題」：在給定的 arr 字元陣列中選擇，儘可能多的覆蓋一個 $1 \times 26$ 的矩陣。

對於此類「精確覆蓋」問題，換個角度也可以看做「組合問題」。

通常有幾種做法：DFS、剪枝 DFS、二進位制列舉、模擬退火、DLX。

其中一頭一尾解法過於簡單和困難，有興趣的同學自行了解與實現。

剪枝 DFS

根據題意，可以有如下的剪枝策略：

1. 預處理掉「本身具有重複字元」的無效字串，並去重；
2. 由於只關心某個字元是否出現，而不關心某個字元在原字串的位置，因此可以將字串使用 int 進行表示；
3. 由於使用 int 進行表示，因而可以使用「位運算」來判斷某個字元是否可以被追加到當前狀態中；
4. DFS 過程中維護一個 total，代表後續未經處理的字串所剩餘的“最大價值”是多少，從而實現剪枝；
5. 使用 lowbit 計算某個狀態對應的字元長度是多少；
6. 使用「全域性雜湊表」記錄某個狀態對應的字元長度是多少（使用 static 修飾，確保某個狀態在所有測試資料中只會被計算一次）；
7. 【未應用】由於存在第 $4$ 點這樣的「更優性剪枝」，理論上我們可以根據「字串所包含字元數量」進行從大到小排序，然後再進行 DFS 這樣效果理論上會更好。想象一下如果存在一個包含所有字母的字串，先選擇該字串，後續所有字串將不能被新增，那麼由它出發的分支數量為 $0$；而如果一個字串只包含單個字母，先決策選擇該字串，那麼由它出發的分支數量必然大於 $0$。但該策略實測效果不好，沒有新增到程式碼中。

程式碼： ```Java class Solution { // 本來想使用如下邏輯將「所有可能用到的狀態」打表，實現 O(1) 查詢某個狀態有多少個字元，但是被卡了 // static int N = 26, M = (1 << N); // static int[] cnt = new int[M]; // static { // for (int i = 0; i < M; i++) { // for (int j = 0; j < 26; j++) { // if (((i >> j) & 1) == 1) cnt[i]++; // } // } // }

static Map<Integer, Integer> map = new HashMap<>();
int get(int cur) {
    if (map.containsKey(cur)) {
        return map.get(cur);
    }
    int ans = 0;
    for (int i = cur; i > 0; i -= lowbit(i)) ans++;
    map.put(cur, ans);
    return ans;
}
int lowbit(int x) {
    return x & -x;
}

int n;
int ans = Integer.MIN_VALUE;
int[] hash;
public int maxLength(List<String> _ws) {
    n = _ws.size();
    HashSet<Integer> set = new HashSet<>();
    for (String s : _ws) {
        int val = 0;
        for (char c : s.toCharArray()) {
            int t = (int)(c - 'a');
            if (((val >> t) & 1) != 0) {
                val = -1;
                break;
            } 
            val |= (1 << t);
        }
        if (val != -1) set.add(val);
    }

    n = set.size();
    if (n == 0) return 0;
    hash = new int[n];

    int idx = 0;
    int total = 0;
    for (Integer i : set) {
        hash[idx++] = i;
        total |= i;
    }
    dfs(0, 0, total);
    return ans;
}
void dfs(int u, int cur, int total) {
    if (get(cur | total) <= ans) return;
    if (u == n) {
        ans = Math.max(ans, get(cur));
        return;
    }
    // 在原有基礎上，選擇該數字（如果可以）
    if ((hash[u] & cur) == 0) {
        dfs(u + 1, hash[u] | cur, total - (total & hash[u]));
    }
    // 不選擇該數字
    dfs(u + 1, cur, total);
}

} ```

二進位制列舉

首先還是對所有字串進行預處理。

然後使用「二進位制列舉」的方式，列舉某個字串是否被選擇。

舉個🌰，$(110){2}$ 代表選擇前兩個字串，$(011){2}$ 代表選擇後兩個字串，這樣我們便可以枚舉出所有組合方案。

程式碼： ```Java class Solution { static Map map = new HashMap<>(); int get(int cur) { if (map.containsKey(cur)) { return map.get(cur); } int ans = 0; for (int i = cur; i > 0; i -= lowbit(i)) ans++; map.put(cur, ans); return ans; } int lowbit(int x) { return x & -x; }

int n;
int ans = Integer.MIN_VALUE;
Integer[] hash;
public int maxLength(List<String> _ws) {
    n = _ws.size();
    HashSet<Integer> set = new HashSet<>();
    for (String s : _ws) {
        int val = 0;
        for (char c : s.toCharArray()) {
            int t = (int)(c - 'a');
            if (((val >> t) & 1) != 0) {
                val = -1;
                break;
            } 
            val |= (1 << t);
        }
        if (val != -1) set.add(val);
    }

    n = set.size();
    if (n == 0) return 0;
    hash = new Integer[n];
    int idx = 0;
    for (Integer i : set) hash[idx++] = i;

    for (int i = 0; i < (1 << n); i++) {
        int cur = 0, val = 0;
        for (int j = 0; j < n; j++) {
            if (((i >> j) & 1) == 1) {
                if ((cur & hash[j]) == 0) {
                    cur |= hash[j];
                    val += get(hash[j]);
                } else {
                    cur = -1;
                    break;
                }
            }
        }
        if (cur != -1) ans = Math.max(ans, val);
    }
    return ans;
}

} ```

模擬退火

事實上，可以將原問題看作求「最優字首序列」問題，從而使用「模擬退火」進行求解。

具體的，我們可以定義「最優字首序列」為 組成最優解所用到的字串均出現在排列的前面。

舉個🌰，假如構成最優解使用到的字串集合為 [a,b,c]，那麼對應 [a,b,c,...]、[a,c,b,...] 均稱為「最優字首序列」。

不難發現，答案與最優字首序列是一對多關係，這指導我們可以將「引數」調得寬鬆一些。

具有「一對多」關係的問題十分適合使用「模擬退火」，使用「模擬退火」可以輕鬆將本題 arr.length 資料範圍上升到 $60$ 甚至以上。

調整成比較寬鬆的引數可以跑贏「二進位制列舉」，但為了以後增加資料不容易被 hack，還是使用 N=400 & fa=0.90 的搭配。

「模擬退火」的幾個引數的作用在 這裡 說過了，不再贅述。

程式碼： ```Java class Solution { static Map map = new HashMap<>(); int get(int cur) { if (map.containsKey(cur)) { return map.get(cur); } int ans = 0; for (int i = cur; i > 0; i -= lowbit(i)) ans++; map.put(cur, ans); return ans; } int lowbit(int x) { return x & -x; }

int n;
int ans = Integer.MIN_VALUE;    
Random random = new Random(20210619);
double hi = 1e4, lo = 1e-4, fa = 0.90; 
int N = 400; 
int calc() {
    int mix = 0, cur = 0;
    for (int i = 0; i < n; i++) {
        int hash = ws[i];
        if ((mix & hash) == 0) {
            mix |= hash;
            cur += get(hash);
        } else {
            break;
        }
    }
    ans = Math.max(ans, cur);
    return cur;
}
void shuffle(int[] nums) {
    for (int i = n; i > 0; i--) {
        int idx = random.nextInt(i);
        swap(nums, idx, i - 1);
    }
}
void swap(int[] nums, int a, int b) {
    int c = nums[a];
    nums[a] = nums[b];
    nums[b] = c;
}
void sa() {
    shuffle(ws);
    for (double t = hi; t > lo; t *= fa) {
        int a = random.nextInt(n), b = random.nextInt(n);
        int prev = calc(); 
        swap(ws, a, b);
        int cur = calc(); 
        int diff = cur - prev;
        if (Math.log(-diff / t) > random.nextDouble()) swap(ws, a, b);
    }
}
int[] ws;
public int maxLength(List<String> _ws) {
    // 預處理字串：去重，剔除無效字元
    // 結果這一步後：N 可以下降到 100；fa 可以下降到 0.70，耗時約為 78 ms
    // 為了預留將來新增測試資料，題解還是保持 N = 400 & fa = 0.90 的配置
    n = _ws.size();
    HashSet<Integer> set = new HashSet<>();
    for (String s : _ws) {
        int val = 0;
        for (char c : s.toCharArray()) {
            int t = (int)(c - 'a');
            if (((val >> t) & 1) != 0) {
                val = -1;
                break;
            } 
            val |= (1 << t);
        }
        if (val != -1) set.add(val);
    }

    n = set.size();
    if (n == 0) return 0;
    ws = new int[n];
    int idx = 0;
    for (Integer i : set) ws[idx++] = i;

    while (N-- > 0) sa();
    return ans;
}

} ```

最後

這是我們「刷穿 LeetCode」系列文章的第 No.1239 篇，系列開始於 2021/01/01，截止於起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們將先把所有不帶鎖的題目刷完。

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

為了方便各位同學能夠電腦上進行除錯和提交程式碼，我建立了相關的倉庫：https://github.com/SharingSource/LogicStack-LeetCode 。

在倉庫地址裡，你可以看到系列文章的題解連結、系列文章的相應程式碼、LeetCode 原題連結和其他優選題解。

更多更全更熱門的「筆試/面試」相關資料可訪問排版精美的 合集新基地 🎉🎉