Untitled

 avatar
user_2276358
swift
a month ago
4.6 kB
1
Indexable
Never

import Foundation
The first line imports the Foundation framework, which provides essential data types, collections, and operating system services to define the base layer of functionality for our app.
swift
Copy code
// Helper function to check if two strings are similar
func areSimilar(_ s1: String, _ s2: String) -> Bool {
    if s1 == s2 { return true }
Here, we declare a helper function areSimilar that takes two strings, s1 and s2, as inputs and returns a boolean value indicating whether the two strings are similar.
The first condition checks if the strings are identical. If they are, the function immediately returns true.
swift
Copy code
    var diffIndices = [Int]()
    let chars1 = Array(s1)
    let chars2 = Array(s2)
We declare an array diffIndices to store the indices where the two strings differ.
Then, we convert the input strings into arrays of characters to easily access individual characters by index.
swift
Copy code
    for i in 0..<chars1.count {
        if chars1[i] != chars2[i] {
            diffIndices.append(i)
        }
        if diffIndices.count > 2 {
            return false
        }
    }
We iterate over the characters of the strings. If the characters at the same index are different, we record the index in diffIndices.
If the number of differing indices exceeds two, we return false because two strings can only be similar if they differ at exactly two positions (and swapping those characters would make them identical).
swift
Copy code
    return diffIndices.count == 2 && chars1[diffIndices[0]] == chars2[diffIndices[1]] && chars1[diffIndices[1]] == chars2[diffIndices[0]]
}
Finally, we check if there are exactly two differing indices and if swapping the characters at those indices in one string would make the strings identical. If both conditions are met, we return true; otherwise, we return false.
swift
Copy code
// Main function to find the number of groups
func numSimilarGroups(_ strs: [String]) -> Int {
    let n = strs.count
    var adjacencyList = [Int: [Int]]()
Next, we define the main function numSimilarGroups, which takes an array of strings as input and returns the number of groups of similar strings.
We get the number of strings, n, and initialize an empty dictionary adjacencyList to represent the adjacency list of our graph. This list will map each string to the indices of other similar strings.
swift
Copy code
    // Build the adjacency list
    for i in 0..<n {
        for j in i + 1..<n {
            if areSimilar(strs[i], strs[j]) {
                adjacencyList[i, default: []].append(j)
                adjacencyList[j, default: []].append(i)
            }
        }
    }
We build the adjacency list by iterating over each pair of strings in the input array.
If two strings are similar, we add an edge between their indices in the adjacency list. This way, each index is mapped to the indices of its similar strings.
swift
Copy code
    var visited = Array(repeating: false, count: n)
    var groups = 0
We create an array visited to keep track of which strings have been visited during our traversal, initializing all values to false.
We also initialize a variable groups to count the number of connected components (or groups) in the graph.
swift
Copy code
    // Depth-First Search (DFS)
    func dfs(_ node: Int) {
        visited[node] = true
        for neighbor in adjacencyList[node, default: []] {
            if !visited[neighbor] {
                dfs(neighbor)
            }
        }
    }
We define a helper function dfs to perform a depth-first search (DFS) on the graph.
The function marks the current node as visited and recursively visits all its unvisited neighbors.
swift
Copy code
    // Find all connected components
    for i in 0..<n {
        if !visited[i] {
            groups += 1
            dfs(i)
        }
    }
    
    return groups
}
Finally, we iterate over all the nodes. If a node has not been visited, it means we have found a new connected component, so we increment the groups counter and start a DFS from that node to visit all nodes in the current group.
After traversing all nodes, we return the total number of groups.
swift
Copy code
// Test cases
let testCases = [
    ["tars", "rats", "arts", "star"],
    ["omv", "ovm"],
    ["abc", "bca", "cab", "xyz"]
]

for (index, testCase) in testCases.enumerated() {
    print("Test Case \(index + 1): \(numSimilarGroups(testCase))")
}
Lastly, we define some test cases to validate our function and print the results.
We iterate over the test cases, calling numSimilarGroups for each and printing the result.