3435. 最短超序列的频次

Hard

题目描述

给定一个字符串数组 words。找到所有最短公共超序列（SCS），这些超序列互相之间不是排列关系。

最短公共超序列是一个长度最小的字符串，它包含 words 中的每个字符串作为子序列。

返回一个二维整数数组 freqs 表示所有的 SCS。每个 freqs[i] 是一个大小为 26 的数组，表示单个 SCS 中小写英文字母的频次。你可以以任意顺序返回频次数组。

示例 1：

输入：words = ["ab","ba"]
输出：[[1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]
解释：两个 SCS 是 "aba" 和 "bab"。输出是每个 SCS 的字母频次。

示例 2：

输入：words = ["aa","ac"]
输出：[[2,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]
解释：两个 SCS 是 "aac" 和 "aca"。由于它们互为排列，只保留 "aac"。

示例 3：

输入：words = ["aa","bb","cc"]
输出：[[2,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]
解释："aabbcc" 及其所有排列都是 SCS。

约束条件：

1 <= words.length <= 256
words[i].length == 2
所有字符串中总共不超过 16 个不同的小写字母
words 中的所有字符串都是唯一的

提示：

每个 SCS 中每个字符最多出现 2 次。为什么？
构造每个可能字符的所有子集（1 或 2 个）。
使用拓扑排序检查是否可以构造超序列。

解题思路

这道题的核心思路基于以下几个关键观察：

字符频次上界：由于每个输入字符串长度为2，在最短公共超序列中，每个字符最多出现2次。超过2次就不是最短的了。
枚举字符频次：对于每个出现过的字符，我们需要确定它在超序列中出现1次还是2次。这可以通过位运算枚举所有可能的组合。
拓扑排序验证：对于每个字符频次组合，我们需要验证是否能构造出满足条件的超序列。这通过构建有向图并进行拓扑排序来实现：
- 图的节点是字符的出现位置
- 边表示字符间的顺序关系（来自输入字符串的约束）
去重处理：由于题目要求不返回互为排列的结果，我们只需要返回字符频次数组，自然避免了排列重复。

算法步骤：

收集所有出现过的字符
枚举每个字符出现1次或2次的所有组合
对每个组合，构建约束图并检查是否存在有效的拓扑排序
将有效的字符频次转换为26位数组格式

代码实现

class Solution {
public:
    vector<vector<int>> supersequences(vector<string>& words) {
        set<char> chars;
        for (const string& word : words) {
            for (char c : word) {
                chars.insert(c);
            }
        }
        
        vector<char> charList(chars.begin(), chars.end());
        int n = charList.size();
        vector<vector<int>> result;
        
        // 枚举每个字符出现1次或2次
        for (int mask = 0; mask < (1 << n); mask++) {
            vector<int> counts(n);
            for (int i = 0; i < n; i++) {
                counts[i] = (mask & (1 << i)) ? 2 : 1;
            }
            
            if (canConstruct(words, charList, counts)) {
                vector<int> freq(26, 0);
                for (int i = 0; i < n; i++) {
                    freq[charList[i] - 'a'] = counts[i];
                }
                result.push_back(freq);
            }
        }
        
        return result;
    }
    
private:
    bool canConstruct(const vector<string>& words, const vector<char>& charList, const vector<int>& counts) {
        unordered_map<char, int> charIndex;
        for (int i = 0; i < charList.size(); i++) {
            charIndex[charList[i]] = i;
        }
        
        // 构建图：节点是字符位置，边是顺序约束
        int totalNodes = 0;
        for (int count : counts) {
            totalNodes += count;
        }
        
        vector<vector<int>> graph(totalNodes);
        vector<int> indegree(totalNodes, 0);
        
        // 为每个字符分配节点编号
        vector<vector<int>> charNodes(charList.size());
        int nodeId = 0;
        for (int i = 0; i < charList.size(); i++) {
            for (int j = 0; j < counts[i]; j++) {
                charNodes[i].push_back(nodeId++);
            }
        }
        
        // 根据输入字符串添加约束边
        for (const string& word : words) {
            int idx1 = charIndex[word[0]];
            int idx2 = charIndex[word[1]];
            
            // word[0] must come before word[1]
            for (int node1 : charNodes[idx1]) {
                for (int node2 : charNodes[idx2]) {
                    graph[node1].push_back(node2);
                    indegree[node2]++;
                }
            }
        }
        
        // 拓扑排序检查是否存在有效排列
        queue<int> q;
        int processed = 0;
        
        for (int i = 0; i < totalNodes; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }
        
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            processed++;
            
            for (int next : graph[node]) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    q.push(next);
                }
            }
        }
        
        return processed == totalNodes;
    }
};

class Solution:
    def supersequences(self, words: List[str]) -> List[List[int]]:
        chars = set()
        for word in words:
            chars.update(word)
        
        char_list = sorted(list(chars))
        n = len(char_list)
        result = []
        
        # 枚举每个字符出现1次或2次
        for mask in range(1 << n):
            counts = []
            for i in range(n):
                counts.append(2 if mask & (1 << i) else 1)
            
            if self.can_construct(words, char_list, counts):
                freq = [0] * 26
                for i in range(n):
                    freq[ord(char_list[i]) - ord('a')] = counts[i]
                result.append(freq)
        
        return result
    
    def can_construct(self, words, char_list, counts):
        char_index = {char_list[i]: i for i in range(len(char_list))}
        
        # 构建图：节点是字符位置，边是顺序约束
        total_nodes = sum(counts)
        graph = [[] for _ in range(total_nodes)]
        indegree = [0] * total_nodes
        
        # 为每个字符分配节点编号
        char_nodes = []
        node_id = 0
        for count in counts:
            nodes = []
            for _ in range(count):
                nodes.append(node_id)
                node_id += 1
            char_nodes.append(nodes)
        
        # 根据输入字符串添加约束边
        for word in words:
            idx1 = char_index[word[0]]
            idx2 = char_index[word[1]]
            
            # word[0] must come before word[1]
            for node1 in char_nodes[idx1]:
                for node2 in char_nodes[idx2]:
                    graph[node1].append(node2)
                    indegree[node2] += 1
        
        # 拓扑排序检查是否存在有效排列
        from collections import deque
        queue = deque()
        processed = 0
        
        for i in range(total_nodes):
            if indegree[i] == 0:
                queue.append(i)
        
        while queue:
            node = queue.popleft()
            processed += 1
            
            for next_node in graph[node]:
                indegree[next_node] -= 1
                if indegree[next_node] == 0:
                    queue.append(next_node)
        
        return processed == total_nodes

public class Solution {
    public IList<IList<int>> Supersequences(string[] words) {
        HashSet<char> chars = new HashSet<char>();
        foreach (string word in words) {
            foreach (char c in word) {
                chars.Add(c);
            }
        }
        
        List<char> charList = chars.ToList();
        charList.Sort();
        int n = charList.Count;
        List<IList<int>> result = new List<IList<int>>();
        
        // 枚举每个字符出现1次或2次
        for (int mask = 0; mask < (1 << n); mask++) {
            int[] counts = new int[n];
            for (int i = 0; i < n; i++) {
                counts[i] = (mask & (1 << i)) != 0 ? 2 : 1;
            }
            
            if (CanConstruct(words, charList, counts)) {
                int[] freq = new int[26];
                for (int i = 0; i < n; i++) {
                    freq[charList[i] - 'a'] = counts[i];
                }
                result.Add(freq.ToList());
            }
        }
        
        return result;
    }
    
    private bool CanConstruct(string[] words, List<char> charList, int[] counts) {
        Dictionary<char, int> charIndex = new Dictionary<char, int>();
        for (int i = 0; i < charList.Count; i++) {
            charIndex[charList[i]] = i;
        }
        
        // 构建图：节点是字符位置，边是顺序约束
        int totalNodes = counts.Sum();
        List<List<int>> graph = new List<List<int>>();
        int[] indegree = new int[totalNodes];
        
        for (int i = 0; i < totalNodes; i++) {
            graph.Add(new List<int>());
        }
        
        // 为每个字符分配节点编号
        List<List<int>> charNodes = new List<List<int>>();
        int nodeId = 0;
        for (int i = 0; i < counts.Length; i++) {
            List<int> nodes = new List<int>();
            for (int j = 0; j < counts[i]; j++) {
                nodes.Add(nodeId++);
            }
            charNodes.Add(nodes);
        }
        
        // 根据输入字符串添加约束边
        foreach (string word in words) {
            int idx1 = charIndex[word[0]];
            int idx2 = charIndex[word[1]];
            
            // word[0] must come before word[1]
            foreach (int node1 in charNodes[idx1]) {
                foreach (int node2 in charNodes[idx2]) {
                    graph[node1].Add(node2);
                    indegree[node2]++;
                }
            }
        }
        
        // 拓扑排序检查是否存在有效排列
        Queue<int> queue = new Queue<int>();
        int processed = 0;
        
        for (int i = 0; i < totalNodes; i++) {
            if (indegree[i] == 0) {
                queue.Enqueue(i);
            }
        }
        
        while (queue.Count > 0) {
            int node = queue.Dequeue();
            processed++;
            
            foreach (int next in graph[node]) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.Enqueue(next);
                }
            }
        }
        
        return processed == totalNodes;
    }
}

var supersequences = function(words) {
    const n = words.length;
    const memo = new Map();
    
    function solve(mask) {
        if (mask === (1 << n) - 1) {
            return [new Array(26).fill(0)];
        }
        
        if (memo.has(mask)) {
            return memo.get(mask);
        }
        
        const results = [];
        const chars = new Set();
        
        for (let i = 0; i < n; i++) {
            if (!(mask & (1 << i))) {
                for (const char of words[i]) {
                    chars.add(char);
                }
            }
        }
        
        for (const char of chars) {
            const charCode = char.charCodeAt(0) - 97;
            let newMask = mask;
            
            for (let i = 0; i < n; i++) {
                if (!(mask & (1 << i))) {
                    const word = words[i];
                    let canAdvance = false;
                    
                    for (let j = 0; j < word.length; j++) {
                        let foundAll = true;
                        for (let k = 0; k < j; k++) {
                            let found = false;
                            for (let l = 0; l < n; l++) {
                                if ((mask & (1 << l))) {
                                    if (words[l].includes(word[k])) {
                                        found = true;
                                        break;
                                    }
                                }
                            }
                            if (!found) {
                                foundAll = false;
                                break;
                            }
                        }
                        
                        if (foundAll && word[j] === char) {
                            if (j === word.length - 1) {
                                newMask |= (1 << i);
                            }
                            canAdvance = true;
                            break;
                        }
                    }
                    
                    if (!canAdvance) {
                        let hasChar = false;
                        for (const c of word) {
                            if (c === char) {
                                hasChar = true;
                                break;
                            }
                        }
                        if (hasChar && word[0] === char) {
                            if (word.length === 1) {
                                newMask |= (1 << i);
                            }
                        }
                    }
                }
            }
            
            const subResults = solve(newMask);
            for (const freq of subResults) {
                const newFreq = [...freq];
                newFreq[charCode]++;
                results.push(newFreq);
            }
        }
        
        memo.set(mask, results);
        return results;
    }
    
    function findSCS(words) {
        const positions = words.map(() => 0);
        const result = [];
        
        function backtrack() {
            if (positions.every((pos, i) => pos === words[i].length)) {
                return [[]];
            }
            
            const nextChars = new Set();
            for (let i = 0; i < words.length; i++) {
                if (positions[i] < words[i].length) {
                    nextChars.add(words[i][positions[i]]);
                }
            }
            
            const allResults = [];
            for (const char of nextChars) {
                const newPositions = [...positions];
                for (let i = 0; i < words.length; i++) {
                    if (positions[i] < words[i].length && words[i][positions[i]] === char) {
                        newPositions[i]++;
                    }
                }
                
                const oldPositions = [...positions];
                for (let i = 0; i < positions.length; i++) {
                    positions[i] = newPositions[i];
                }
                
                const subResults = backtrack();
                
                for (let i = 0; i < positions.length; i++) {
                    positions[i] = oldPositions[i];
                }
                
                for (const subResult of subResults) {
                    allResults.push([char, ...subResult]);
                }
            }
            
            return allResults;
        }
        
        return backtrack();
    }
    
    const allSCS = findSCS(words);
    const freqMap = new Map();
    
    for (const scs of allSCS) {
        const freq = new Array(26).fill(0);
        for (const char of scs) {
            freq[char.charCodeAt(0) - 97]++;
        }
        
        const key = freq.join(',');
        if (!freqMap.has(key)) {
            freqMap.set(key, freq);
        }
    }
    
    return Array.from(freqMap.values());
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

指标	复杂度
时间	-
空间	-

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析