C++ 异形词典

2025年3月17日 | 阅读 12 分钟

外星词典问题不仅是一个有趣的问题，而且是一个激动人心的问题；在这个问题中，我们需要根据外星语言中某个特定字符的顺序，给出一份该语言单词列表。这些单词是按字典顺序排列的，但要遵循外星语言的规则，这些规则决定了字符的优先顺序。我们被赋予的任务是，考虑到单词列表，尝试找出这个外星语言字符的顺序。

假设我们被传送到一个未知的星球，那里的居民制定了如何排列字母的规则。但我们发现，他们在给定的模式中也同样一致。例如，处理外星单词序列：["baa," "abcd," "abaca," "cab," "cad"]，我们需要理解哪些字符在前，哪些在后。

问题在于，我们得到的是一个词汇顺序的单词列表，但我们不知道字符的排序方式。例如，在英语字母表中，我们已经知道 'a' 在 'b' 之前，'b' 在 'c' 之前，以此类推。但在外星词典中，我们必须对这些规则做出假设。这在依赖性解决中变得非常重要，因为每个字母以一种复合的方式依赖于其他字母。
这个挑战在现实场景中也很相似，我们需要根据一组排序数据来预测关系。例如，根据依赖关系推断软件的构建顺序，或者根据可用的日志来安排事件序列；诸如此类的例子。

图的表示

外星词典问题可以通过图论的概念轻松解决，特别是图的一种——有向无环图。在这个图中，外星语言中的每个字符都可以看作是一个图的节点。从节点 n1 到节点 n2 的箭头表示字符 n1 和 n2 之间存在优先关系。如果某个特定字符（例如 u）必须在外星语言中排在另一个字符（例如 v）之前，那么就从节点 u 到节点 v 画一条连接线。

这种图的构建是通过比较列表中相邻的单词来完成的。这样做，这种方法能够找出两个连续单词之间第一个不同字符的顺序。
例如，如果单词 w1 和 w2 之间第一个不同的字符在 w1 中是 c1，在 w2 中是 c2，那么就确定 c1 在外星语言中排在 c2 之前。然后，这种关系被表示为一条有向线，连接图中节点 c1 和节点 c2。之后，我们将此方法扩展到对所有其他相邻单词对进行相同的分析，直到我们得到一个图，该图描绘了文本中所有推断出的优先关系。
一旦我们有了图，字符顺序的问题就是找到拓扑排序。拓扑排序本身允许按序列对图的节点进行排序，使得对于每条有向边 u -> v，节点 u 在线性序列中排在节点 v 之前。
如果存在有效的拓扑排序，其线性序列可以用来在外星语言中对字符数组进行排序。然而，如果在图中发现循环，则意味着不存在可能的字符顺序，因为结果关系将是不一致的。

拓扑排序

在许多问题场景中，解决方案需要根据元素的依赖关系进行线性排序，而拓扑排序在这种情况下尤为重要，特别是在外星词典的情况下。在图论中，拓扑排序是指找到一个有向图的顶点序列，使得对于任意一条边 u->v，u 在 v 之前。

由于我们将问题已经转化为图，其中任何有向边都表示一个字符对另一个字符的依赖关系，现在我们的工作就归结为确定图中顶点可以排列的顺序。
然而，在外星词典问题中，最重要的事情是，这个拓扑顺序表示了外星语言中字符的位置。但对于简单的图，如果图是无环的（即没有循环），那么我们可以得到一个有效的拓扑排序。如果图是有环的，这意味着给定的单词列表存在不一致的优先关系，因此无法确定图的顺序。

边缘情况

在解决外星词典问题时，应考虑以下几点作为边：让我们概述最常见的几种情况

空输入：如果单词列表为空，则没有字符顺序，该单词列表无效。在这种情况下，输出应为“ ”或错误消息，表明无法形成顺序。
单个单词输入：如果单词列表只包含一个单词，我们无法从该单词列表中得出任何关于字符优先级的结论。然而，该单词的组成元素仍然是外星语言的有效符号。因此，预计输出将由构成整个单词的字符集组成。
单字符单词：如果单词列表包含仅由单个字符组成的单词，例如 ["a," "b," "c"]，则这些字符应包含在输出中。虽然它们之间没有直接关系，但它们都作为外星语言的有效字符，应该出现在结果中。
前缀规则违规：无疑，处理正则表达式最具挑战性的怪癖之一是当违反了某个前缀规则的情况。例如，单词列表可能包含 "ABC" 和 "ab" 这样的单词。根据词汇顺序，不可能将 "abc" 排在 "ab" 之前，因为第二个单词是第一个单词的前缀。以下显示了计算步骤，其中输入无效，算法应返回不一致的指示。
图中的循环：需要注意的是，图中的边意味着冲突的优先关系，因此无法形成有效的排序。这也是在进行拓扑排序时需要检测循环以妥善处理这种情况的原因之一。在检测到循环的情况下，算法应返回一个指示，告知用户无法建立有效顺序。

解决问题的步骤

外星词典问题的解决方案是基于图论，特别是拓扑排序来确定字符的顺序。那么，让我们更仔细地一步一步地讨论它是如何工作的。

步骤 1：识别字符之间的关系

解决问题的第一个方法是根据相邻单词中的位置来识别字符之间的关系。由于单词是根据外星语言的词汇顺序排列的，我们可以通过比较两个相邻单词的字符来推断字符的优先级。这里的概念是定位给定两个单词不同的第一个字符。
例如，如果单词 w1 在列表中排在单词 w2 之前，并且 w1 和 w2 中第一个不同的字符分别是 c1 和 c2，那么在外星语言中，c1 出现在 c2 之前。

例如

例如，在单词 ["baa," "abcd"] 中，比较两个单词 "baa" 和 "abcd" 的第一个字符，我们可以看到第一个字母是 'b'，它排在字母 'a' 之前。
在单词 "abcd" 和 "abaca" 中，前两个字符相同，但第三个字符不同，这意味着 'c' 在 'd' 之前。
这样，通过比较这些单词对中的每一对，我们就能逐步建立字符的优先关系。

步骤 2：构建图

在推导出字符关系后，下一步是将其表示为图的形式。这里我们使用有向无环图 (DAG)。
图中的圆圈代表外星语言中的一个字符，一个节点代表它。
从一个节点（字符）到另一个节点（字符）的有向边意味着一个字符在外星语言中应该排在另一个字符之前。例如，节点 b 和节点 a 之间的边 (b -> a) 意味着 'b' 在 'a' 之前。
这个图是逐步构建的，当我们比较短语中的两个连续单词时。对于推导出的每种关系，都会向图中添加一个相应的有向边。

步骤 3：推荐列表。

在构建图时，需要考虑几种情况

输入不一致：例如，如果第一个单词比第二个单词长，并且它们共享相同的前缀，这是输入中的一个异常。例如，单词列表 "abc" 和 "ab" 中的单词 "abc" 和 "ab" 将始终以无法以任何词汇正确顺序排列的方式出现。
单字符单词：如果单词列表包含非常短的单词，可以确保所有没有优先关系的单个字符最终都会被考虑在内。

步骤 4：循环检测

在构建图之后，检查该图是否正确实现为有向无环图 (DAG) 非常重要。然后，如果图中存在任何循环，则意味着字符顺序无效。图中的循环意味着存在冲突的优先关系；例如，如果 'a' 在 'b' 之前，'b' 在 'c' 之前，但同时 'c' 在 'a' 之前，则无法推导出顺序关系。
这些不规则性可以在拓扑排序期间处理，特别是在循环检测方面。如果识别到任何循环，算法应返回一个信号，表明无法建立有效顺序。

步骤 5：拓扑排序

最后，为了获得字符的顺序，对图进行拓扑排序。如前所述，拓扑排序可确保对于 G 的每条有向边 u->v，u 在最终顺序中排在 v 之前。如果我们成功地实现了拓扑排序，它就是外星语言中字符的正确顺序。

有两种主要方法可以进行拓扑排序

Kahn 算法 (基于 BFS)：这种方法涉及删除所有没有入边（入度为 0）的节点，并将它们放入拓扑顺序中。每当删除一个入度为 0 的节点时，它就会影响所有相邻节点入度值减少一。在这种情况下，当一个邻居的入度降至 0 时，它就被添加到队列中进行处理。这会一直进行，直到所有节点都在解决方案网络中被遍历。如果存在入度非零的节点，则意味着图至少包含一个循环。
基于 DFS 的拓扑排序：遍历图的另一种策略是对图进行深度优先搜索 (DFS)。思路是从给定的节点开始，然后遍历与其相连的所有节点，并遍历与它们相连的所有节点。在访问完当前节点的所有邻居之后，将当前节点添加到拓扑顺序中。这消除了在依赖项添加到列表之前将节点添加到映射列表的可能性。因此，DFS 用于找出是否存在循环；如果在 DFS 遍历期间找到循环，我们将知道不存在有效的排序。

C++ 外星词典代码

 
#include <iostream> 
#include <unordered_map> 
#include <unordered_set> 
#include <vector> 
#include <queue> 
  
using namespace std; 
  
// Function to build the graph and compute the indegrees of each character 
bool build graph(const vector<string>& words, unordered_map<char, unordered_set<char>>& graph, unordered_map<char, int>& indegree) { 
// Initialize the graph and indegree for all unique characters in words 
for (const string& word : words) { 
for (char ch : word) { 
if (graph.find(ch) == graph.end()) { 
graph[ch] = unordered_set<char>(); 
indegree[ch] = 0; 
} 
} 
} 
  
// Compare adjacent words to build the graph 
for (size_t i = 0; i < words.size() - 1; ++i) { 
const string& first = words[i]; 
const string& second = words[i + 1]; 
         
// Check if the second word is a prefix of the first word, which is an invalid case 
if (first.size() > second.size() && first.substr(0, second.size()) == second) { 
return false;  // Invalid lexicographical order 
} 
         
// Find the first different character between the two words 
for (size_t j = 0; j < min(first.size(), second.size()); ++j) { 
if (first[j] != second[j]) { 
char u = first[j]; 
char v = second[j]; 
                 
// If there's no edge from u to v yet, add it 
if (graph[u].find(v) == graph[u].end()) { 
graph[u].insert(v); 
indegree[v]++;  // Increase indegree of v 
} 
                break;  // Once we find the first difference, we stop comparing 
} 
} 
} 
     
return true; 
} 
  
// Function to perform topological sort using Kahn's Algorithm (BFS) 
string topologicalSort(const unordered_map<char, unordered_set<char>>& graph, unordered_map<char, int>& indegree) { 
queue<char> q; 
string result; 
     
// Start with nodes having zero indegree (no incoming edges) 
for (const auto& entry : indegree) { 
if (entry.second == 0) { 
            q.push(entry.first); 
} 
} 
     
while (!q.empty()) { 
char current = q.front(); 
        q.pop(); 
result += current; 
         
// For each neighbor, reduce its indegree by 1 
for (char neighbor : graph.at(current)) { 
indegree[neighbor]--; 
if (indegree[neighbor] == 0) { 
                q.push(neighbor); 
} 
} 
} 
     
// If the result length is less than the total number of unique characters, it indicates a cycle 
if (result.length() < graph.size()) { 
return "";  // Cycle detected 
} 
     
return result; 
} 
  
string alienOrder(const vector<string>& words) { 
    unordered_map<char, unordered_set<char>> graph; 
    unordered_map<char, int> indegree; 
     
// Build the graph from the word list 
if (!buildGraph(words, graph, indegree)) { 
return "Invalid word order - prefix rule violation."; 
} 
     
// Perform topological sort to find the character order 
string order = topologicalSort(graph, indegree); 
     
if (order.empty()) { 
return "Cycle detected - no valid order exists."; 
} 
     
return order; 
} 
  
int main() { 
// Test cases 
vector<vector<string>> testCases = { 
{"wrt", "wrf", "er", "ett", "rftt"}, 
{"z", "x", "z"},  // Cycle case 
{"abc", "ab"},    // Invalid order due to prefix rule 
{"baa", "abcd", "abca", "cab", "cad"}, 
{"a", "b", "c"}, 
{"abc", "def", "ghi"}  // Independent characters 
}; 
  
for (const auto& testCase : testCases) { 
string result = alienOrder(testCase); 
        cout << "Words: "; 
for (const string& word : testCase) { 
            cout << word << " "; 
} 
        cout << "\nAlien Order: " << result << endl << endl; 
} 
     
return 0; 
}    

输出

 
Words: wrt wrf er ett rftt  
Alien Order: wertf 
  
Words: z x z  
Alien Order: Cycle detected - no valid order exists. 
  
Words: abc ab  
Alien Order: Invalid word order - prefix rule violation. 
  
Words: baa abcd abca cab cad  
Alien Order: bdac 
  
Words: a b c  
Alien Order: abc 
  
Words: abc def ghi  
Alien Order: abcdefghi

复杂度分析

外星词典解决方案的时间复杂度为 C + N * L；其中 C 是唯一字符的数量，N 是单词的数量，L 是单词中的最大字符数。这包括图的构建和拓扑排序。由于图的构建包括单词比较以识别优先关系，因此此过程需要 O(N * L)；拓扑排序也需要计算边，其复杂度为 O(C + E)，其中 E = O(N * L)。其空间复杂度也为 O(C + N * L)，用于存储图、入度映射以及处理过程中使用的队列。

结论

总之，我们讨论的外星词典问题通过一组按词汇顺序排列的单词，规定了确定外星语言中字符顺序。解决这个问题的方法是创建一个 DAG，其中每个字符都是图的节点，边表示前驱关系。因此，通过比较两个单词或一个单词及其后续单词，我们可以发现顺序。重要的是，BFS（Kahn 算法）和 DFS 都通过拓扑排序提供了正确的字符顺序。在存在循环或无效前缀条件的情况下，无法形成有效顺序。这对于确保我们正确地从所使用的单词列表中推导出字符层次结构至关重要。

下一主题C++ 中查找二元矩阵中所有 1 形成的“+”的最大尺寸

C++ 异形词典

图的表示

拓扑排序

边缘情况

解决问题的步骤

例如

步骤 2：构建图

C++ 外星词典代码

复杂度分析

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 异形词典

图的表示

拓扑排序

边缘情况

解决问题的步骤

例如

步骤 2：构建图

C++ 外星词典代码

复杂度分析

结论

相关帖子

C++ 类中的辅助函数

C++ std::polar 函数

C++ Dancing Links 算法 (DLX)

C++ Cooley-Tukey FFT 算法

C++ 中的匈牙利算法

C++ 中查找前 N 个 Iccanobif 数的程序

C++ Bogosort 算法

C++ 中的 std::money_put 函数

C++ std::strided_slice 函数

C++ 中 Union 数据类型与 Variant 的区别

订阅 Tpoint Tech