• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode524.通过删除字母匹配到字典里最长单词|LongestWordinDictionarythrou ...

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

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

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

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:

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

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

示例 1:

输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

输出: 
"apple"

示例 2:

输入:
s = "abpcplea", d = ["a","b","c"]

输出: 
"a"

说明:

  1. 所有输入的字符串只包含小写字母。
  2. 字典的大小不会超过 1000。
  3. 所有输入的字符串长度不会超过 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 = str
14             }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 = 0
27     var secondIndex : Int = 0
28     
29     while firstIndex < first.count{
30         if first[firstIndex] == second[secondIndex]{
31             firstIndex += 1
32             secondIndex += 1
33         }else if first[firstIndex] < second[secondIndex]{
34             return first
35         }else{
36             return second
37         }
38     }
39     return first
40 }
41 
42 func canBeFoundFrom(s : [Character], with d : [Character])->Bool{
43     
44     
45     var sIndex : Int = 0
46     var dIndex : Int = 0
47     while sIndex < s.count{
48         if d[dIndex] == s[sIndex]{
49             dIndex += 1
50         }
51         sIndex += 1
52         if dIndex == d.count{
53             return true
54         }
55     }
56     
57     return dIndex == d.count
58   }
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.count
10             let j = items.count
11             if i > j || (i == j && long < items) {
12                 continue
13             }
14             if isValid(s: s, d: items) {
15                 long = items
16             }
17         }
18         
19         return long
20     }
21     
22     fileprivate func isValid(s: String, d: String) -> Bool {
23         var i = 0
24         var j = 0
25         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 += 1
31                 result.append(source[i])
32             }
33             i += 1
34         }
35         return j == target.count
36     }
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 false
11         }
12     }
13     
14     for str in sortedD{
15         if possibleToForm(s, str: str){
16             return str
17         }
18     }
19     return ""
20 }
21 
22 func possibleToForm(_ base : String, str : String)->Bool{
23     guard  base.count >= str.count else {
24         return false
25     }
26     
27     var baseIndex : String.Index = base.startIndex
28     var strIndex : String.Index = str.startIndex
29     
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.endIndex
38   }
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 += 1
13                 }
14             }
15             if i == str.count && str.count >= res.count
16             {
17                 if str.count > res.count || str < res
18                 {
19                     res = str
20                 }
21             }   
22         }
23         return res
24     }
25 }

 

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift3.0 URLSession学习笔记发布时间:2022-07-14
下一篇:
iOS开发-在Swift里使用AFNetworking方法发布时间:2022-07-14
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap