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.
這個(gè)題目的大體意思是 給你兩個(gè)字符串。求后面字符串 包含前面字母的個(gè)數(shù)。
solve
1.開始想著遍歷前面的字符串然后去遍歷后面的字符串。兩個(gè)for循環(huán)。但是這樣做的時(shí)間復(fù)雜度是 m*n。
2.換種思路。把前面的字符串變成Set 然后遍歷后面的字符串 看是否存在即可。此種方式的復(fù)雜度為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
}
不禁獻(xiàn)上了我的膝蓋。
