golang力扣leetcode 剑指Offer II 114. 外星文字典

简介: golang力扣leetcode 剑指Offer II 114. 外星文字典

剑指Offer II 114. 外星文字典

剑指Offer II 114. 外星文字典

题解

题目:这题题目属实写的跟屎一样,样例给的也有问题

现在有一种外星文,与a…z顺序不同,给出一个用外星文构造的字符串列表。

注意:

  1. 字符串内部的字符排列,不是根据外星文排序的
  2. 字符串与字符串之间,谁排在前面,谁排在后面,是根据外星文排序的

请根据该字符串数组,还原出外星人字典序。如果不存在合法字母顺序,返回”“,答案可能有多个,返回任意一个。

在两个字符串相同下标的字符,称为ch1和ch2,在第二种情况中,排在前面的字符串,必定ch1 < ch2 。如果字符相同,len(word1) < len(word2) 。

思路:

其实很容易想到拓扑排序,恶心的是题目描述,重点在于注意那里
1. 既然字符串内部的字符串排列顺序是未知的
2. 那么只能通过相同字符串来建边
3. abc,ab这种样例是不应该出现的,但是样例里面有,题目说给定的是按照排序后的数组,那只能算这种是不合法的了。
4. 对于这种情况,就判断len(word1) > len(word2)
5. 一旦在相同下标有不相等的字符,就立马建边,break,由于现在下标字符的优先级,后面的字符是不可靠的了
6. 建边之后拓扑排序即可

代码

func alienOrder(words []string) string {
  inDeg := make(map[byte]int)
  graph := make(map[byte][]byte)
  for _, word := range words {
    for _, ch := range word {
      inDeg[byte(ch)] = 0 //统计外星文一共有多少字符
    }
  }
  for i := 0; i < len(words)-1; i++ {
    word1 := words[i]
    word2 := words[i+1]
    flag := false
    for j := 0; ; j++ {
      ch1 := word1[j]
      ch2 := word2[j]
      if ch1 != ch2 { //判断两个单词的字符是否一样
        graph[ch1] = append(graph[ch1], ch2) //不同则建边
        inDeg[ch2]++                         //入度加一
        break
      }
      if j == len(word1)-1 || j == len(word2)-1 { //如果flag为true说明字符都相同
        flag = true
        break
      }
    }
    if flag && len(word1) > len(word2) { //abc ab的情况,不合法
      return ""
    }
  }
  ans := make([]byte, 0)
  for k, v := range inDeg {
    if v == 0 { //对于入度为0的字符来说,我们无法确定其顺序,直接加入即可
      ans = append(ans, k)
    }
  }
  queue := make([]byte, len(ans))
  copy(queue, ans)
  for len(queue) > 0 { //拓扑排序
    u := queue[0]
    queue = queue[1:]
    for _, v := range graph[u] {
      inDeg[v]--
      if inDeg[v] == 0 {
        ans = append(ans, v)
        queue = append(queue, v)
      }
    }
  }
  if len(ans) == len(inDeg) { //如果存在环,那么ans必定缺少字符
    return string(ans)
  }
  return ""
}
目录
相关文章
|
4月前
|
Go
【LeetCode 热题100】DP 实战进阶:最长递增子序列、乘积最大子数组、分割等和子集(力扣300 / 152/ 416 )(Go语言版)
本文深入解析三道经典的动态规划问题:**最长递增子序列(LIS)**、**乘积最大子数组** 和 **分割等和子集**。 - **300. LIS** 通过 `dp[i]` 表示以第 `i` 个元素结尾的最长递增子序列长度,支持 O(n²) 动态规划与 O(n log n) 的二分优化。 - **152. 乘积最大子数组** 利用正负数特性,同时维护最大值与最小值的状态转移方程。 - **416. 分割等和子集** 转化为 0-1 背包问题,通过布尔型 DP 实现子集和判断。 总结对比了三题的状态定义与解法技巧,并延伸至相关变种问题,助你掌握动态规划的核心思想与灵活应用!
139 1
|
4月前
|
分布式计算 算法 Go
【LeetCode 热题100】BFS/DFS 实战:岛屿数量 & 腐烂的橘子(力扣200 / 994 )(Go语言版)
本文讲解了两道经典的图论问题:**岛屿数量(LeetCode 200)** 和 **腐烂的橘子(LeetCode 994)**,分别通过 DFS/BFS 实现。在“岛屿数量”中,利用深度或广度优先搜索遍历二维网格,标记连通陆地并计数;“腐烂的橘子”则采用多源 BFS,模拟腐烂传播过程,计算最短时间。两者均需掌握访问标记技巧,是学习网格搜索算法的绝佳实践。
145 1
|
5月前
|
Go 开发者 索引
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣33 / 81/ 153/154)(Go语言版)
本文深入探讨了LeetCode中四道关于「搜索旋转排序数组」的经典题目,涵盖了无重复和有重复元素的情况。通过二分查找的变形应用,文章详细解析了每道题的解题思路和Go语言实现代码。关键点包括判断有序区间、处理重复元素以及如何缩小搜索范围。文章还总结了各题的异同,并推荐了类似题目,帮助读者全面掌握二分查找在旋转数组中的应用。无论是初学者还是有经验的开发者,都能从中获得实用的解题技巧和代码实现方法。
257 14
|
4月前
|
Go
【LeetCode 热题100】BFS/DFS 实战:岛屿数量 & 腐烂的橘子(力扣200 / 994 )(Go语言版)
本篇博客详细解析了三道经典的动态规划问题:198. 打家劫舍(线性状态转移)、279. 完全平方数与322. 零钱兑换(完全背包问题)。通过 Go 语言实现,帮助读者掌握动态规划的核心思想及其实战技巧。从状态定义到转移方程,逐步剖析每道题的解法,并总结其异同点,助力解决更复杂的 DP 问题。适合初学者深入理解动态规划的应用场景和优化方法。
89 0
|
4月前
|
算法 Go 索引
【LeetCode 热题100】回溯:括号生成 & 组合总和(力扣22 / 39 )(Go语言版)
本文深入解析了LeetCode上的两道经典回溯算法题:**22. 括号生成**与**39. 组合总和**。括号生成通过维护左右括号数量,确保路径合法并构造有效组合;组合总和则允许元素重复选择,利用剪枝优化搜索空间以找到所有满足目标和的组合。两者均需明确路径、选择列表及结束条件,同时合理运用剪枝策略提升效率。文章附有Go语言实现代码,助你掌握回溯算法的核心思想。
109 0
|
6月前
|
Go
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣437 / 236 )(Go语言版)
本文深入探讨二叉树中路径与祖先问题,涵盖两道经典题目:LeetCode 437(路径总和 III)和236(最近公共祖先)。对于路径总和 III,文章分析了双递归暴力解法与前缀和优化方法,后者通过哈希表记录路径和,将时间复杂度从O(n²)降至O(n)。在最近公共祖先问题中,采用后序遍历递归查找,利用“自底向上”的思路确定最近公共祖先节点。文中详细解析代码实现与核心要点,帮助读者掌握深度追踪技巧,理解树结构中路径与节点关系的本质。这类问题在面试中高频出现,掌握其解法意义重大。
124 4
|
6月前
|
算法 Go
【LeetCode 热题100】深入理解二叉树结构变化与路径特性(力扣104 / 226 / 114 / 543)(Go语言版)
本博客深入探讨二叉树的深度计算、结构变换与路径分析,涵盖四道经典题目:104(最大深度)、226(翻转二叉树)、114(展开为链表)和543(二叉树直径)。通过递归与遍历策略(前序、后序等),解析每题的核心思路与实现方法。结合代码示例(Go语言),帮助读者掌握二叉树相关算法的精髓。下一讲将聚焦二叉树构造问题,欢迎持续关注!
139 10
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
188 6
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
140 6
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
306 2

推荐镜像

更多