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

[Swift]LeetCode792.匹配子序列的单词数|NumberofMatchingSubsequences

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

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

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

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

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

Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.

Example :
Input: 
S = "abcde"
words = ["a", "bb", "acd", "ace"]
Output: 3
Explanation: There are three words in words that are a subsequence of S: "a", "acd", "ace".

Note:

  • All words in words and S will only consists of lowercase letters.
  • The length of S will be in the range of [1, 50000].
  • The length of words will be in the range of [1, 5000].
  • The length of words[i] will be in the range of [1, 50].

给定字符串 S 和单词字典 words, 求 words[i] 中是 S 的子序列的单词个数。

示例:
输入: 
S = "abcde"
words = ["a", "bb", "acd", "ace"]
输出: 3
解释: 有三个是 S 的子序列的单词: "a", "acd", "ace"。

注意:

  • 所有在words和 S 里的单词都只由小写字母组成。
  • S 的长度在 [1, 50000]
  • words 的长度在 [1, 5000]
  • words[i]的长度在[1, 50]

Runtime: 740 ms
Memory Usage: 20 MB
 1 class Solution {
 2     func numMatchingSubseq(_ S: String, _ words: [String]) -> Int {
 3         let arrS:[Character] = Array(S)
 4         var res:Int = 0
 5         var n:Int = S.count
 6         var pass:Set<String> = Set<String>()
 7         var out:Set<String> = Set<String>()
 8         for word in words
 9         {
10             let arrW:[Character] = Array(word)
11             if pass.contains(word) || out.contains(word)
12             {
13                 if pass.contains(word) {res += 1}
14                 continue
15             }
16             var i:Int = 0
17             var j:Int = 0
18             var m:Int = word.count
19             while (i < n && j < m)
20             {
21                 if arrW[j] == arrS[i] {j += 1}
22                 i += 1
23             }
24             if j == m 
25             {
26                 res += 1
27                 pass.insert(word)
28             }
29             else
30             {
31                 out.insert(word)
32             }            
33         }
34         return res
35     }
36 }

1168ms

 1 class Solution {
 2     func numMatchingSubseq(_ S: String, _ words: [String]) -> Int {
 3         var indices = [Character: [Int]]()
 4         let S = Array(S.characters)
 5         for i in 0..<S.count {
 6             indices[S[i], default:[]].append(i)
 7         }
 8         
 9         func binarySearch(_ ch: Character, _ from: Int) -> Int {
10             guard let arr = indices[ch] else { return -2 }
11             if from > arr.last! { return -2 }
12             
13             var l = 0, r = arr.count - 1
14             while l < r {
15                 let mid = (l + r) / 2
16                 if arr[mid] < from {
17                     l = mid + 1
18                 } else {
19                     r = mid
20                 }
21             }
22             return arr[r]
23         }
24         
25         var res = 0
26         for w in words {
27             var from = 0
28             for ch in w.characters {
29                 from = binarySearch(ch, from) + 1
30                 if from < 0 { break }
31             }
32             if from >= 0 { res += 1 }
33         }
34         return res
35     }
36 }

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
UIKit应用-Swift版本:3.让UITableViewCell的背景色渐变发布时间:2022-07-13
下一篇:
Swift 是猴还是猿?发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

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

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

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