[Swift]LeetCode953.验证外星语词典|VerifyinganAlienDictionary

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

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

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

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

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

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

In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.

Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographicaly in this alien language.

Example 1:

Input: words = true
Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.

Example 2:

Input: words = false
Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.

Example 3:

Input: words = false
Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character (More info).

Note:

1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
All characters in words[i] and order are english lowercase letters.

某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。

给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。

示例 1：

输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
输出：true
解释：在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。

示例 2：

输入：words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
输出：false
解释：在该语言的字母表中，'d' 位于 'l' 之后，那么 words[0] > words[1]，因此单词序列不是按字典序排列的。

示例 3：

输入：words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
输出：false
解释：当前三个字符 "app" 匹配时，第二个字符串相对短一些，然后根据词典编纂规则 "apple" > "app"，因为 'l' > '∅'，其中 '∅' 是空白字符，定义为比任何其他字符都小（更多信息）。

提示：

1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
在 words[i] 和 order 中的所有字符都是英文小写字母。

28ms

 1 class Solution {
 2     func isAlienSorted(_ words: [String], _ order: String) -> Bool {
 3         var ret = true
 4         
 5         for i in 1 ..< words.count {
 6             ret = isInOrder(words[i-1], words[i], order)
 7             if !ret { return false }
 8         }
 9         
10         return true
11     }
12     
13     func isInOrder(_ word1: String, _ word2: String, _ order: String) -> Bool{
14         
15         let word1 = Array(word1)
16         let word2 = Array(word2)
17         
18         var i = 0, j = 0
19         while i < word1.count && j < word2.count {
20             if order.firstIndex(of: word1[i])! == order.firstIndex(of: word2[j])! {
21                 i += 1
22                 j += 1
23             }else if order.firstIndex(of: word1[i])! < order.firstIndex(of: word2[j])!{
24                 return true
25             }else {
26                 return false
27             }
28         }
29         
30         if word1.count == word2.count {
31             return true
32         } else if word1.count > word2.count{
33             return false
34         }
35         
36         return true
37     }
38 }

32ms

 1 class Solution {
 2     private var map = [Character: Int]()
 3     func isAlienSorted(_ words: [String], _ order: String) -> Bool {
 4         for (index, char) in order.enumerated() {
 5             map[char] = index
 6         }
 7         
 8         for (index, word) in words.enumerated() where index < words.count-1 {
 9             if !wordsInOrder(word1: word, word2: words[index+1]) {
10                 return false
11             }
12         }
13         
14         return true
15     }
16     
17     private func wordsInOrder(word1: String, word2: String) -> Bool {
18         let one = Array(word1)
19         let two = Array(word2)
20         
21         var index = 0
22         var areEqual = true
23         
24         while index < one.count || index < two.count {
25             if areEqual && two.count == index && one.count > index {
26                 return false
27             } else if areEqual && one.count == index && two.count > index {
28                 return true
29             } 
30             
31             let first = one[index]
32             let second = two[index]
33             
34             index += 1
35             
36             if first == second {
37                 continue
38             } else {
39                 areEqual = false
40             }
41             
42             if map[first]! < map[second]! {
43                 return true
44             } else if map[first]! == map[second]! {
45                 continue
46             } else {
47                 return false
48             }
49         }
50         
51         return true
52     }
53 }

40ms

 1 class Solution {
 2   func isAlienSorted(_ words: [String], _ order: String) -> Bool {
 3     var dict: [Character: Int] = [:]
 4     
 5     for (i, char) in order.enumerated() {
 6       dict[char] = i
 7     }
 8     
 9     outer: for i in 0..<words.count - 1 {
10       var j = 0
11       let currWord = Array(words[i])
12       let nextWord = Array(words[i + 1])
13       
14       while j < currWord.count && j < nextWord.count {
15         let currVal = dict[currWord[j]]!
16         let nextVal = dict[nextWord[j]]!
17         if currVal > nextVal {
18           return false
19         } else if currVal < nextVal {
20           continue outer
21         }
22         j += 1
23       }
24       
25       return false
26     }
27     
28     return true
29   }
30 }

44ms

 1 class Solution {
 2     
 3     var orderDic : [Character:Int] = [:]
 4     
 5     func isAlienSorted(_ words: [String], _ order: String) -> Bool {
 6         var currentOrder = 0
 7         for (idx,ord) in order.enumerated() {
 8             orderDic[ord] = idx
 9         }
10         
11         for i in 0..<words.count-1 {
12             if !self.isOrdered(words[i], words[i+1]) {
13                 return false
14             }
15         }
16         
17         return true
18     }
19     
20     func isOrdered(_ word1 : String, _ word2: String) -> Bool {
21         let word2Chars = Array(word2)
22         for (idx, char) in word1.enumerated() {
23             if idx >= word2.count {
24                 return false
25             }
26             
27             if orderDic[char]! > orderDic[word2Chars[idx]]! {
28                 return false
29             } else if orderDic[char]! < orderDic[word2Chars[idx]]! {
30                 return true
31             }
32         }
33         
34         return true
35     }
36 }

48ms

 1 class Solution {
 2     func isAlienSorted(_ words: [String], _ order: String) -> Bool {
 3 
 4         var map = [Character: Int]()
 5         let orderChars = Array(order)
 6         for i in 0..<orderChars.count {
 7             map[orderChars[i]] = i
 8         }
 9 
10         for i in 1..<words.count {
11             if !isAscend(words[i-1], words[i], map: map) {
12                 return false
13             }
14         }
15         return true
16     }
17 
18     func isAscend(_ str1: String, _ str2: String, map:[Character: Int]) -> Bool {
19 
20         let char1 = Array(str1)
21         let char2 = Array(str2)
22 
23         let len = min(char1.count, char2.count)
24 
25         for i in 0..<len {
26             if map[char1[i]]! > map[char2[i]]!{
27                 return false
28             }
29             if map[char1[i]]! < map[char2[i]]!{
30                 return true
31             }
32         }
33         return char1.count <= char2.count
34     }
35 }

52ms

 1 class Solution {
 2 func isAlienSorted(_ words: [String], _ order: String) -> Bool {
 3     var index = 0
 4     var dict = [Character: Int]()
 5     for char in order {
 6         dict[char] = index
 7         index += 1
 8     }
 9     //
10     if words.count == 1 {return true}
11     var base = words[0]
12     for i in 1..<words.count {
13         var curIndex = words[i].startIndex
14         while !base.isEmpty && base != words[i] {
15             
16             if dict[base.first!]! < dict[words[i][curIndex]]! {
17                 base = words[i]
18                 continue
19             } else if dict[base.first!] == dict[words[i].first!] {
20                 base.removeFirst()
21               if curIndex == words[i].index(words[i].startIndex, offsetBy: words[i].count - 1) && !base.isEmpty { return false }
22                curIndex = words[i].index(after: curIndex) 
23                 
24             } else {
25                 return false
26             }
27             
28         }
29     }
30     return true
31 }
32 }

72ms

 1 class Solution {
 2     func isAlienSorted(_ words: [String], _ order: String) -> Bool {
 3         var words = words
 4         var a:[Int] = [Int](repeating:0,count:256)
 5         var i:Int = 0
 6         var j:Int = 0
 7         for i in 0..<order.count
 8         {
 9             a[order[i].ascii] = i
10         }
11         for i in 0..<words.count
12         {
13             for j in 0..<words[i].count
14             {
15                 //a:97
16                 words[i][j] = (a[words[i][j].ascii] + 97).ASCII
17             }
18         }
19          for i in 0..<(words.count - 1)
20         {
21             if words[i] > words[i+1]
22             {
23                 return false
24             }
25         }
26         return true
27     }
28 }
29 extension String {        
30     //subscript函数可以检索数组中的值
31     //直接按照索引方式截取指定索引的字符
32     subscript (_ i: Int) -> Character {
33         //读取字符
34         get {return self[index(startIndex, offsetBy: i)]}
35         
36         //修改字符
37         set
38         {
39             var str:String = self
40             var index = str.index(startIndex, offsetBy: i)
41             str.remove(at: index)
42             str.insert(newValue, at: index)
43             self = str
44         }
45     }
46 }
47 
48 //Character扩展方法  
49 extension Character  
50 {  
51   //属性：ASCII整数值(定义小写为整数值)
52    var ascii: Int {
53         get {
54             let s = String(self).unicodeScalars
55             return Int(s[s.startIndex].value)
56         }
57     }
58 }
59 
60 //Int扩展方法  
61 extension Int
62 {
63     //属性：ASCII值(定义大写为字符值)
64     var ASCII:Character 
65     {
66         get {return Character(UnicodeScalar(self)!)}
67     }
68 }