Hey Maria, let's break down your questions step by step—this is such a great deep dive into Swift string performance! I'll cover the complexity of your two implementations, the native methods you're using, and the range-based counting approach you're curious about.

1. Time & Space Complexity of Two numJewelsInStones Implementations #

First, let's assume the two common implementations you're working with (I'll use standard Swift patterns here):

Implementation 1: Filter + String.contains #

func numJewelsInStones(_ jewels: String, _ stones: String) -> Int {
    return stones.filter { jewels.contains($0) }.count
}

• Time Complexity: Let’s say jewels has length J and stones has length S. The filter method iterates over all S characters in stones. For each character, jewels.contains($0) does a linear scan of jewels (since String’s contains checks each character one by one by default). That gives us a total time complexity of O(S*J).
• Space Complexity: The filter method creates a new collection to store matching characters, so in the worst case (all stones are jewels), this uses O(S) space.

Implementation 2: Set Preprocessing #

func numJewelsInStones(_ jewels: String, _ stones: String) -> Int {
    let jewelSet = Set(jewels)
    return stones.filter { jewelSet.contains($0) }.count
}

• Time Complexity: First, converting jewels to a Set takes O(J) time (each insertion into a hash set is average O(1)). Then, filter iterates over S characters, and Set.contains($0) is average O(1) thanks to hash lookups. Total time complexity is O(J + S)—a huge improvement over the first implementation, especially when J is large.
• Space Complexity: The Set stores all J jewel characters, plus the filter result uses up to O(S) space. Total space is O(J + S).

2. Time Complexity of Swift Native String Methods #

You mentioned using filter, mapping to a character array, and contains—here's how they perform:

• String.filter(_:): This method iterates through every character in the string, applies your closure, and collects matches. Time complexity is O(N) where N is the string’s length. Space complexity is O(N) in the worst case (all characters pass the filter).
• String.map { $0 } (to Character Array): This iterates through each character and adds it to an array. Time complexity is O(N), space complexity is O(N) since we’re creating a new array with all characters.
• String.contains(_:): For standard characters (like ASCII), this does a linear scan of the string, so O(N) time. For complex Unicode characters (like combined graphemes), there’s a tiny bit of extra processing under the hood, but it’s still linear time overall.

3. Complexity of Using String.range(of:) to Count Characters #

If you’re using repeated calls to range(of:) to count how many times a character appears in stones, like this:

func countCharacter(_ char: Character, in string: String) -> Int {
    var count = 0
    var currentRange = string.startIndex..<string.endIndex
    while let range = string.range(of: String(char), range: currentRange) {
        count += 1
        currentRange = range.upperBound..<string.endIndex
    }
    return count
}

• Time Complexity: Each range(of:) call does a linear scan starting from currentRange.lowerBound. In the worst case (every character in the string is the target), this means we scan S characters first, then S-1, then S-2, etc. Adding those up gives O(S²) time—this is really inefficient for large strings.
• Space Complexity: We only use a few variables (count, currentRange), so extra space is O(1).

Quick Recommendation #

If you’re optimizing numJewelsInStones, the Set-based implementation is the way to go—it’s the most efficient for almost all cases. Avoid the range-based counting approach unless you’re dealing with extremely small strings, since its quadratic time gets painful fast.

内容的提问来源于stack exchange，提问作者Maria 9905