You're given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.
The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".
Example 1:
Input: J = "aA", S = "aAAbbbb"
Output: 3
Example 2:
Input: J = "z", S = "ZZ"
Output: 0
Note:
S and J will consist of letters and have length at most 50.
The characters in J are distinct.
这个题目的大体意思是 给你两个字符串。求后面字符串 包含前面字母的个数。
solve
1.开始想着遍历前面的字符串然后去遍历后面的字符串。两个for循环。但是这样做的时间复杂度是 m*n。
2.换种思路。把前面的字符串变成Set 然后遍历后面的字符串 看是否存在即可。此种方式的复杂度为m+n。代码如下。
func numJewelsInStones(_ J: String, _ S: String) -> Int {
let jSet = Set(J)
let sArr = Array(S)
var count = 0
for item in sArr{
if jSet.contains(item){
count = count+1
}
}
return count
}
- 在讨论中看到了一种超级赞的解法。代码如下。
func numJewelsInStones(_ J: String, _ S: String) -> Int {
return S.replacingOccurrences(of:"[^"+J+"]", with: "").count
}
不禁献上了我的膝盖。
