Swift Coding Test Course, Try

Problem Description

In this lecture, we will learn about the Trie data structure and solve algorithmic problems using the Trie.

The problem is as follows:

Problem: Phone Number List
Write a function to check if any phone number in a given list is a prefix of another phone number.
If any of the consecutive phone numbers have a prefix relationship, return false, 
otherwise return true.

Input:
- An array of phone number strings, numbers. (1 ≤ numbers.length ≤ 1000, 1 ≤ numbers[i].length ≤ 30)

Output:
- Return false if phone numbers have a prefix relationship, otherwise return true.

Problem Solving Process

1. Understanding the Trie Data Structure

A Trie is a tree structure optimized for storing and searching strings. Each node in the Trie represents a path to the next character, making it useful for storing strings like phone numbers.
A key feature of the Trie is that it can effectively save memory when there are strings that share a common prefix.

2. Implementing the Trie

To implement a Trie, we define a node class and design the Trie as a structure that includes node objects.

class TrieNode {
    var children: [Character: TrieNode] = [:]
    var isEndOfNumber: Bool = false
}

3. Implementing the insert Method

We implement the insert method to insert a new phone number into the Trie. This method adds each character of the phone number to the node, and sets isEndOfNumber to true at the end of the phone number.

class Trie {
    var root: TrieNode
    
    init() {
        root = TrieNode()
    }
    
    func insert(_ number: String) {
        var currentNode = root
        for char in number {
            if currentNode.children[char] == nil {
                currentNode.children[char] = TrieNode()
            }
            currentNode = currentNode.children[char]!
        }
        currentNode.isEndOfNumber = true
    }
}

4. Implementing the checkPrefix Method

Next, we implement the checkPrefix method to check if a phone number in the list is a prefix of another phone number.
This method traverses the Trie and checks if the current string is the end of a phone number before reaching the end of another phone number to determine the prefix relationship.

func checkPrefix(_ number: String) -> Bool {
    var currentNode = root
    for (index, char) in number.enumerated() {
        if let node = currentNode.children[char] {
            currentNode = node
            // If the current node is an ending phone number
            if currentNode.isEndOfNumber {
                return false
            }
        } else {
            break
        }
        // If there are nodes existing beyond the last character
        if index < number.count - 1 && currentNode.isEndOfNumber {
            return false
        }
    }
    return true
}

5. Overall Solution

Finally, we insert all phone numbers into the Trie for the given list of phone numbers and call checkPrefix for each phone number to return the result.

func solution(_ numbers: [String]) -> Bool {
    let trie = Trie()
    
    for number in numbers {
        // Check if it is a prefix of an already registered phone number
        if !trie.checkPrefix(number) {
            return false
        }
        // Register the current phone number
        trie.insert(number)
    }
    return true
}

6. Time Complexity and Space Complexity

The time complexity of this algorithm using a Trie is O(N * M), where N is the number of phone numbers and M is the maximum length of the phone numbers.
The space complexity is O(N * M), representing the space needed to store the phone numbers.

Conclusion

In this lecture, we explored how to solve the problem of determining prefix relationships among a list of phone numbers using the Trie data structure.
Tries are a powerful tool for string processing and can be applied to various string-related problems.
Especially when dealing with a large number of strings, considering space complexity allows for efficient design.