查看: 2924| 回复: 6
跳转到指定楼层
上一主题 下一主题
收起左侧

[高频题] Alien Dictionary

全局:
高频题
公司名称: airbnb

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
请问有大神可以解释一下alien dictionary怎么找所有可能的排序吗?看地里都是说用backtracking,可是小弟我还是不太理解



补充内容 (2019-9-27 01:59):
alien dictionary all possible orderingy

上一篇:最近还有 Leetcode Premium Student Discount吗?
下一篇:新手学python求问一个关于prime的题目?
推荐
nagato 2019-9-27 13:53:46 | 只看该作者
全局:
本帖最后由 nagato 于 2019-9-27 00:59 编辑
zhimingli123 发表于 2019-9-27 00:00
比如 [a, bc, d], 就得返回 abdc, abcd, acbd, abcd. 这都是可能也valid的order,怎么样才可以把这些都找 ..
  1. import collections
  2. def alienOrder(words):
  3.     g = collections.defaultdict(set)
  4.     ind = collections.defaultdict(int)
  5.    
  6.     for i in range(1, len(words)):
  7.         for j in range(min(len(words[i-1]), len(words[i]))):
  8.             if words[i-1][j] != words[i][j]:
  9.                 g[words[i-1][j]].add(words[i][j])
  10.                 ind[words[i][j]] += 1
  11.                 break
  12.     start = []
  13.     res = []
  14.     char_set = set("".join(w for w in words))
  15.     for c in char_set:
  16.         if ind[c] == 0:
  17.             start.append(c)

  18.     def dfs(usable, indegree, path):
  19.         if not usable:
  20.             if len(path) == len(char_set):
  21.                 res.append(path)
  22.             return
  23.         for i in range(len(usable)):
  24.             cur = usable[i]
  25.             tmp = dict(indegree)
  26.             new_usable = []
  27.             for nei in g[cur]:
  28.                 tmp[nei] -= 1
  29.                 if tmp[nei] == 0:
  30.                     new_usable.append(nei)
  31.             dfs(usable[:i] + usable[i+1:] + new_usable, tmp, path + cur)

  32.     dfs(start, ind ,"")        
  33.     return res

  34. print(alienOrder(["wrt","wrf","er","ett","rftt"])) #['wertf']
  35. print(alienOrder(["a", "bc", "d"])) #['acbd', 'abcd', 'abdc', 'cabd']
  36. print(alienOrder(["yx", "yz"])) #['xyz', 'xzy', 'yxz']
复制代码


这样?

评分

参与人数 11大米 +19 收起 理由
vanbupt + 2 垃圾回复/毫无意义的水贴
hyklxf + 3 给你点个赞!
SpartanGiraffe + 1 给你点个赞!
ashzhao + 2 给你点个赞!
bhavanaNavuluri + 1 很有用的信息!

查看全部评分

回复

使用道具 举报

推荐
magicsets 2019-9-27 14:04:19 | 只看该作者
全局:
本帖最后由 magicsets 于 2019-9-27 14:07 编辑

这个问题数学上称作“偏序集的线性扩展”(Linear Extensions of Partial Order Set),参考这里:http://mathworld.wolfram.com/LinearExtension.html

首先问题本身是#P-complete的,时间复杂度与所生成的order数量有关,而最坏情况下order数量是指数级的

但是仍然有办法区分在这个问题上一些算法的好坏,就是给定一个输入,记不同字符的个数为K,记最终生成的全部order数量为 N

那么有三种级别的算法:

(1) Naive方法:基于Kahn拓扑排序算法改一改,时间复杂度 K^2 * N

(我在下面写了一份naive方法的代码..)

(2) An Algorithm to Generate All Topological Sorting Arrangement:思想类似于非递归生成全排序的Heap算法,时间复杂度 K * N

(3) Generating Linear Extensions Fast:号称时间复杂度为 常数 * N

----

Naive方法代码:
  1. import java.util.ArrayList;
  2. import java.util.HashMap;
  3. import java.util.HashSet;
  4. import java.util.StringJoiner;

  5. class AlienDictionary {
  6.   // 有向图
  7.   private HashSet<Character> vertices = new HashSet<>();
  8.   private HashMap<Character, HashSet<Character>> edges = new HashMap<>();

  9.   // 枚举拓扑序时使用的数据结构
  10.   char[] topologyOrder;
  11.   ArrayList<String> topologyOrderList;
  12.   boolean[] isVisited;
  13.   int[] indegrees;
  14.   
  15.   public void AddVertex(char vertex) {
  16.     vertices.add(vertex);
  17.     edges.computeIfAbsent(vertex, k -> new HashSet<>());
  18.   }
  19.   
  20.   public void AddEdge(char src, char dst) {
  21.     edges.get(src).add(dst);
  22.   }
  23.   
  24.   public ArrayList<String> EnumerateTopologyOrder() {
  25.     // 枚举拓扑序时使用的数据结构
  26.     topologyOrder = new char[vertices.size()];
  27.     topologyOrderList = new ArrayList<>();
  28.     isVisited = new boolean[256];
  29.     indegrees = new int[256];

  30.     // 初始化 indegrees
  31.     for (char vertex : vertices) {
  32.       for (char neighbor : edges.get(vertex)) {
  33.         ++indegrees[(int)neighbor];
  34.       }
  35.     }
  36.    
  37.     // 开始递归枚举
  38.     for (char v : vertices) {
  39.       if (indegrees[(int)v] == 0) {
  40.         EnumerateTopologyOrderInternal(0, v);
  41.       }
  42.     }
  43.     return topologyOrderList;
  44.   }
  45.   
  46.   private void EnumerateTopologyOrderInternal(int index, char vertex) {
  47.     topologyOrder[index++] = vertex;
  48.     if (index == vertices.size()) {
  49.       StringJoiner sj = new StringJoiner(" < ");
  50.       for (char c : topologyOrder) {
  51.         sj.add(String.valueOf(c));
  52.       }
  53.       topologyOrderList.add(sj.toString());
  54.       return;
  55.     }
  56.     for (char neighbor : edges.get(vertex)) {
  57.       --indegrees[(int)neighbor];      
  58.     }
  59.     isVisited[(int)vertex] = true;
  60.     for (char candidate : vertices) {
  61.       if (!isVisited[(int)candidate] && indegrees[(int)candidate] == 0) {
  62.         EnumerateTopologyOrderInternal(index, candidate);
  63.       }
  64.     }
  65.     isVisited[(int)vertex] = false;
  66.     for (char neighbor : edges.get(vertex)) {
  67.       ++indegrees[(int)neighbor];      
  68.     }
  69.   }
  70. }


  71. public class Main {
  72.   private static int FindFirstDiffPos(String lhs, String rhs) {
  73.     for (int i = 0; i < Math.min(lhs.length(), rhs.length()); ++i) {
  74.       if (lhs.charAt(i) != rhs.charAt(i)) {
  75.         return i;
  76.       }
  77.     }
  78.     return -1;
  79.   }
  80.   
  81.   public static AlienDictionary CreateAlienDictionary(String[] words) {
  82.     AlienDictionary dict = new AlienDictionary();
  83.     if (words.length == 0) {
  84.       return dict;
  85.     }
  86.     for (char c : words[0].toCharArray()) {
  87.       dict.AddVertex(c);
  88.     }   
  89.     for (int i = 1; i < words.length; ++i) {
  90.       for (char c : words[i].toCharArray()) {
  91.         dict.AddVertex(c);
  92.       }
  93.       int pos = FindFirstDiffPos(words[i-1], words[i]);
  94.       if (pos >= 0) {
  95.         dict.AddEdge(words[i-1].charAt(pos), words[i].charAt(pos));
  96.       }
  97.     }
  98.     return dict;
  99.   }  
  100.   
  101.   public static void main(String[] args) {
  102.     AlienDictionary dict = CreateAlienDictionary(
  103.         new String[] {
  104.             "a",
  105.             "b",
  106.             "cd",
  107.             "cdb",
  108.             "cde",
  109.         });

  110.     for (String order : dict.EnumerateTopologyOrder()) {
  111.       System.out.println(order);
  112.     }
  113.    
  114.     // 输出 (注意到输入里面d与其他字符不存在任何偏序关系,所以d可以出现在任何地方):
  115.     //
  116.     // a < b < c < d < e
  117.     // a < b < c < e < d
  118.     // a < b < d < c < e
  119.     // a < b < d < e < c
  120.     // a < b < e < c < d
  121.     // a < b < e < d < c
  122.     // a < d < b < c < e
  123.     // a < d < b < e < c
  124.     // d < a < b < c < e
  125.     // d < a < b < e < c
  126.   }  
  127. }
复制代码


[/i][/i][/i]

评分

参与人数 2大米 +18 收起 理由
14417335 + 16
Airtnp + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

全局:
这题是topological sort吧..先把dictionary扫一遍用Map先得到topological ordering,然后从indegree为0的character开始进行BFS就行了...看看discussion, 都挺清楚的
回复

使用道具 举报

🔗
 楼主| zhimingli123 2019-9-27 09:57:09 来自APP | 只看该作者
全局:
nyubladestealth 发表于 2019/09/27 09:30:33
这题是topological sort吧..先把dictionary扫一遍用Map先得到topological ordering,然后从indegree为0的character开始进行BFS就行了.....
可是没有详细说找所有possible ordering的,你这个方法只是basic的求一个possibility的吧
回复

使用道具 举报

🔗
337845818 2019-9-27 12:21:49 | 只看该作者
全局:
字典不给你全部排序你怎么求? 他给你什么就是什么了。。
回复

使用道具 举报

🔗
 楼主| zhimingli123 2019-9-27 13:00:44 来自APP | 只看该作者
全局:
337845818 发表于 2019/09/27 12:21:49
字典不给你全部排序你怎么求? 他给你什么就是什么了。。
比如 [a, bc, d], 就得返回 abdc, abcd, acbd, abcd. 这都是可能也valid的order,怎么样才可以把这些都找出来,不只是return一个valid的
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表