小型公司网站建设论文,建筑人才网怎么和招聘人说话,电子商务网站功能设计,专业网站建设教程Problem: 269. 火星词典 文章目录 思路解题方法复杂度Code 思路 首先#xff0c;我们先将所有单词中出现的字符标记为 0#xff0c;没有出现的标记为 1。然后#xff0c;我们开始建图#xff0c;对于每一个单词对#xff0c;我们比较它们的前缀#xff0c;直到找到第一个… Problem: 269. 火星词典 文章目录 思路解题方法复杂度Code 思路 首先我们先将所有单词中出现的字符标记为 0没有出现的标记为 1。然后我们开始建图对于每一个单词对我们比较它们的前缀直到找到第一个不同的字符然后将这个字符对应的节点连接到另一个字符对应的节点并更新入度表。最后我们使用拓扑排序来输出字典序最小的字符串。 解题方法 我们使用拓扑排序来解决这个问题。首先我们将所有入度为 0 的节点入队然后依次出队并更新入度表。当所有节点都被出队后我们就可以得到字典序最小的字符串。 复杂度
时间复杂度: O ( n m ) O(n m) O(nm)其中 n 是单词的总长度m 是单词的个数。 空间复杂度: O ( n ) O(n) O(n)其中 n 是单词的总长度。 Code
class Solution {public String alienOrder(String[] words) {// 入度表int[] indegree new int[26];Arrays.fill(indegree, -1);// 将出现的字符表记为0 没有出现的标记为1for (String w : words) {for (int i 0; i w.length(); i) {indegree[w.charAt(i) - a] 0;}}// 建图ListListInteger graph new ArrayList();for (int i 0; i 26; i) {graph.add(new ArrayList());}for (int i 0, j, len; i words.length - 1; i) {String cur words[i];String next words[i 1];j 0;len Math.min(cur.length(), next.length());for (; j len; j) {if (cur.charAt(j) ! next.charAt(j)) {graph.get(cur.charAt(j) - a).add(next.charAt(j) - a);indegree[next.charAt(j) - a];break;}}if (j cur.length() j next.length()) {return ;}}int[] queue new int[26];int l 0, r 0, kinds 0;for (int i 0; i 26; i) {if (indegree[i] ! -1) {kinds;}if (indegree[i] 0) {queue[r] i;}}StringBuilder ans new StringBuilder();while (l r) {int cur queue[l];ans.append((char) (cur a));for (int next : graph.get(cur)) {if (--indegree[next] 0) {queue[r] next;}}}return ans.length() kinds ? ans.toString() : ;}
}
