[Swift]LeetCode269.外星人词典$AlienDictionary

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10640352.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Example 1:

Input:
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

Output: "wertf"

Example 2:

Input:
[
  "z",
  "x"
]

Output: "zx"

Example 3:

Input:
[
  "z",
  "x",
  "z"
] 

Output: "" 

Explanation: The order is invalid, so return "".

Note:

You may assume all letters are in lowercase.
You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
If the order is invalid, return an empty string.
There may be multiple valid order of letters, return any one of them is fine.

有一种新的外来语言使用拉丁字母。但是，您不知道字母之间的顺序。您会从字典中收到一个非空单词列表，其中的单词按照新语言的规则按字典顺序排序。导出这种语言的字母顺序。

例1：

Input:
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

Output: "wertf"

例2：

Input:
[
  "z",
  "x"
]

Output: "zx"

例3：

Input:
[
  "z",
  "x",
  "z"
] 

Output: ""

说明：订单无效，因此请返回“”。
注意：

1、您可以假设所有字母都是小写的。
2、您可以假设如果a是b的前缀，则a必须出现在给定字典中的b之前。
3、如果订单无效，则返回空字符串。
4、可能有多个有效的字母顺序，返回其中任何一个都没问题。

Solution

 1 class Solution {
 2     func alienOrder(_ words: [String]) -> String {
 3         var st:Set<[Character]> = Set<[Character]>()
 4         var ch:Set<Character> = Set<Character>()
 5         var ins:[Int] = [Int](repeating:0,count:256)
 6         var q:[Character] = [Character]()
 7         var res:String = String()
 8         for a in words
 9         {
10             for c in a
11             {
12                 ch.insert(c)
13             }
14         }
15         for i in 0..<words.count - 1
16         {
17             let mn:Int = min(words[i].count, words[i + 1].count)
18             var j:Int = 0
19             while(j < min(words[i].count, words[i + 1].count))
20             {
21                 if words[i][j] != words[i + 1][j]
22                 {
23                     st.insert([words[i][j], words[i + 1][j]])
24                     break
25                 }
26                 j += 1
27             }
28             if j == mn && words[i].count > words[i + 1].count
29             {
30                 return String()
31             }
32         }
33         for a in st
34         {
35             ins[a[1].ascii] += 1
36         }
37         for a in ch
38         {
39             if ins[a.ascii] == 0
40             {
41                 q.append(a)
42                 res.append(a)
43             }
44         }
45         while(!q.isEmpty)
46         {
47             let c:Character = q.removeFirst()
48             for a in st
49             {
50                 if a[0] == c
51                 {
52                     ins[a[1].ascii] -= 1
53                     if ins[a[1].ascii] == 0
54                     {
55                         q.append(a[1])
56                         res.append(a[1])
57                     }
58                 }
59             }
60         }
61         return res.count == ch.count ? res : String()
62     }
63 }
64 
65 //String扩展
66 extension String {
67     //subscript函数可以检索数组中的值
68     //直接按照索引方式截取指定索引的字符
69     subscript (_ i: Int) -> Character {
70         //读取字符
71         get {return self[index(startIndex, offsetBy: i)]}
72     }
73 }
74 
75 //Character扩展
76 extension Character
77 {
78     //Character转ASCII整数值(定义小写为整数值)
79     var ascii: Int {
80         get {
81             return Int(self.unicodeScalars.first?.value ?? 0)
82         }
83     }
84 }

点击：Playground测试

1 var sol = Solution()
2 print(sol.alienOrder(["wrt", "wrf", "er", "ett","rftt"]))
3 //Print wertf
4 print(sol.alienOrder(["z","x"]))
5 //Print zx
6 print(sol.alienOrder(["z","x","z"]))
7 //Print ""