坑很多。。首先是题意。。 其次是很多种情况= =。。头疼
func alienOrder(_ words: [String]) -> String {
//创建边
var edge = Dictionary<Character,Set<Character>>()
//记录入度
var indeg = Dictionary<Character,Int>()
//判断是否合法
var isValid = true
let wLen = words.count
//开始构建图,构建图的规则比较怪
//初始化入度
for word in words {
let array = Array(word)
for c in array {
indeg[c] = 0
}
}
for i in 1..<wLen {
let w1 = Array(words[i - 1]) ,w2 = Array(words[i])
let l1 = w1.count,l2 = w2.count
let minLen = min(l1, l2)
var j = 0
while j < minLen {
//遇到第一个不相等的 左边指向右边创建一条边
let left = w1[j]
let right = w2[j]
if left != right {
if let _ = edge[left] {
//有可能left = right 造成入度+1
if !edge[left]!.contains(right) && left != right {
//入度+1
indeg[right]! += 1
edge[left]!.insert(right)
}
}else {
edge[left] = Set<Character>()
edge[left]!.insert(right)
//入度+1
if left != right {
//入度+1
indeg[right]! += 1
}
}
break
}
j += 1
}
//前一个字符串长度大于当前字符串长度 但前minLength均相等
if l1 > l2 && j == minLen {
isValid = false
}
}
if !isValid {
return ""
}
//图构建完成,寻找入度为0的节点
var tempArray = [Character]()
for keyStr in indeg.keys {
let value = indeg[keyStr]
if value == 0 {
tempArray.append(keyStr)
}
}
//用来记录结果
var res = [Character]()
while !tempArray.isEmpty{
let v = tempArray.removeLast()
res.append(v)
if let nextSet = edge[v] {
for nextV in nextSet {
indeg[nextV]! -= 1
if indeg[nextV] == 0 {
tempArray.insert(nextV, at: 0)
}
}
}
}
return res.count == indeg.count ? String(res) : ""
}
网友评论