[Swift]LeetCode524. 通过删除字母匹配到字典里最长单词 | Longest Word in Dictionary through Deleting

概述Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, retur

Given a string and a string dictionary,find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results,return the longest word with the smallest lexicographical order. If there is no possible result,return the empty string.

Example 1:

input:s = "abpcplea",d = ["ale","apple","monkey","plea"]Output: "apple"

Example 2:

input:s = "abpcplea",d = ["a","b","c"]Output: "a"

Note:

All the strings in the input will only contain lower-case letters. The size of the dictionary won‘t exceed 1,000. The length of all the strings in the input won‘t exceed 1,000.

给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

示例 1:

输入:s = "abpcplea","plea"]输出: "apple"

示例 2:

输入:s = "abpcplea","c"]输出: "a"

说明:

所有输入的字符串只包含小写字母。 字典的大小不会超过 1000。 所有输入的字符串长度不会超过 1000。

340ms

 1 class Solution { 2     func findLongestWord(_ s: String,_ d: [String]) -> String { 3     var result : [Character] = [] 4     let s = Array(s) 5     for str in d { 6         var str = Array(str) 7         if str.count < result.count{ 8             continue 9         }10         11         if canBeFoundFrom(s: s,with: Array(str)){12             if str.count > result.count{13                 result = str14             }else if str.count == result.count{15                 result = lexicoOrder(result,str)16             }17             18         }19     }20     21     return String(result)22 }23 24 func lexicoOrder(_ first : [Character],_ second : [Character])->[Character]{25     26     var firstIndex : Int = 027     var secondindex : Int = 028     29     while firstIndex < first.count{30         if first[firstIndex] == second[secondindex]{31             firstIndex += 132             secondindex += 133         }else if first[firstIndex] < second[secondindex]{34             return first35         }else{36             return second37         }38     }39     return first40 }41 42 func canBeFoundFrom(s : [Character],with d : [Character])->Bool{43     44     45     var sIndex : Int = 046     var dindex : Int = 047     while sIndex < s.count{48         if d[dindex] == s[sIndex]{49             dindex += 150         }51         sIndex += 152         if dindex == d.count{53             return true54         }55     }56     57     return dindex == d.count58   }59 }

532ms

 1 class Solution { 2      func findLongestWord(_ s: String,_ d: [String]) -> String { 3         if d.count == 0 { 4             return "" 5         } 6  7         var long = "" 8         for items in d { 9             let i = long.count10             let j = items.count11             if i > j || (i == j && long < items) {12                 continue13             }14             if isValID(s: s,d: items) {15                 long = items16             }17         }18         19         return long20     }21     22     fileprivate func isValID(s: String,d: String) -> Bool {23         var i = 024         var j = 025         var source = Array(s)26         var target = Array(d)27         var result = ""28         while i < source.count && j < target.count {29             if source[i] == target[j] {30                 j += 131                 result.append(source[i])32             }33             i += 134         }35         return j == target.count36     }37 }

840ms

 1 class Solution { 2     func findLongestWord(_ s: String,_ d: [String]) -> String { 3      4     let sortedD = d.sorted { (first,second) -> Bool in 5         if first.count > second.count{ 6             return true 7         }else if first.count == second.count{ 8             return first < second 9         }else{10             return false11         }12     }13     14     for str in sortedD{15         if possibletoForm(s,str: str){16             return str17         }18     }19     return ""20 }21 22 func possibletoForm(_ base : String,str : String)->Bool{23     guard  base.count >= str.count else {24         return false25     }26     27     var baseIndex : String.Index = base.startIndex28     var strIndex : String.Index = str.startIndex29     30     while baseIndex != base.endindex && strIndex != str.endindex{31         if str[strIndex] == base[baseIndex]{32             strIndex = str.index(after: strIndex)33         }34          baseIndex = base.index(after: baseIndex)35     }36     37     return strIndex == str.endindex38   }39 }

Runtime: 7968 ms Memory Usage: 20.7 MB

 1 class Solution { 2     func findLongestWord(_ s: String,_ d: [String]) -> String { 3         var res:String = String()         4         for str in d 5         { 6             var arr:[Character] = Array(str) 7             var i:Int = 0 8             for c in s.characters 9             {10                 if i < str.count && c == arr[i]11                 {12                     i += 113                 }14             }15             if i == str.count && str.count >= res.count16             {17                 if str.count > res.count || str < res18                 {19                     res = str20                 }21             }   22         }23         return res24     }25 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode524. 通过删除字母匹配到字典里最长单词 | Longest Word in Dictionary through Deleting全部内容，希望文章能够帮你解决[Swift]LeetCode524. 通过删除字母匹配到字典里最长单词 | Longest Word in Dictionary through Deleting所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。