C# Coding Test Course, Try

1. Introduction

As programming languages have grown, a variety of data structures and algorithms have become necessary. Among them, the trie is a data structure specialized in efficiently handling strings, mainly used for string search, autocomplete features, and storing prefix sets. In this article, we will introduce algorithm problems using the trie data structure and solve them using C#.

2. Understanding the Trie Data Structure

A trie has polymorphic properties, with nodes representing each character. Tries have the following characteristics:

• The ability to store all words.
• The ability to easily search for prefixes of words.
• A structure that can group words with the same prefix.

A trie is typically structured as follows:

class TrieNode {
    Dictionary Children;
    bool IsEndOfWord;

    public TrieNode() {
        Children = new Dictionary();
        IsEndOfWord = false;
    }
}
    
class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void Insert(string word) {
        TrieNode current = root;
        foreach (char c in word) {
            if (!current.Children.ContainsKey(c)) {
                current.Children[c] = new TrieNode();
            }
            current = current.Children[c];
        }
        current.IsEndOfWord = true;
    }

    public bool Search(string word) {
        TrieNode current = root;
        foreach (char c in word) {
            if (!current.Children.ContainsKey(c)) {
                return false;
            }
            current = current.Children[c];
        }
        return current.IsEndOfWord;
    }

    public bool StartsWith(string prefix) {
        TrieNode current = root;
        foreach (char c in prefix) {
            if (!current.Children.ContainsKey(c)) {
                return false;
            }
            current = current.Children[c];
        }
        return true;
    }
}
    

3. Problem Introduction

The problem we will cover in this lecture is as follows:

Problem: Count the Number of Words with a Specific Prefix

Given a list of words and a specific prefix, write a function that returns the number of words that start with this prefix.

Input:

• Word list: [“apple”, “app”, “application”, “apricot”]
• Prefix: “app”

Output: 3 (The words “app”, “apple”, and “application” are in the word list.)

4. Problem-Solving Process

To solve the problem, we will use the trie data structure to insert words and implement a function to count the number of words that start with a specific prefix.

1. **Insert Words**: First, we need to insert all the words into the trie. This will create child nodes for each character of every word.

2. **Prefix Search**: Implement the logic to count the number of words that start with the specific prefix by performing a deep search.

3. **Return Result**: Return the count of words that start with the prefix.

4.1 Code Implementation

Below is the complete code implemented in C#:

class Solution {
    public int CountWordsWithPrefix(string[] words, string prefix) {
        Trie trie = new Trie();
        
        // Insert all words into the trie
        foreach (string word in words) {
            trie.Insert(word);
        }
        
        // Counting the number of words that start with the prefix
        return CountWordsStartingWithPrefix(trie, prefix);
    }

    private int CountWordsStartingWithPrefix(Trie trie, string prefix) {
        TrieNode current = trie.Root;
        foreach (char c in prefix) {
            if (!current.Children.ContainsKey(c)) {
                return 0; // Return 0 if there are no words corresponding to the prefix
            }
            current = current.Children[c];
        }
        return CountAllWords(current); // Count all words below the prefix
    }

    private int CountAllWords(TrieNode node) {
        int count = 0;
        
        if (node.IsEndOfWord) {
            count++; // Increase word count if the current node is the end of a word
        }
        
        foreach (var child in node.Children) {
            count += CountAllWords(child.Value); // Recursively explore all child nodes
        }
        
        return count;
    }
}
    

5. Time Complexity Analysis

The time complexity for inserting a word into the trie is O(m), where m is the length of the word.
Searching for a prefix takes O(k) time (where k is the length of the prefix).
Thus, the overall time complexity is O(n * m + k), where n is the number of words.

6. Test Cases

Here are a few test cases:

string[] words = {"apple", "app", "application", "apricot"};
string prefix = "app";
Solution solution = new Solution();
Console.WriteLine(solution.CountWordsWithPrefix(words, prefix)); // Output: 3

words = new string[] {"banana", "bandana", "band"};
prefix = "ban";
Console.WriteLine(solution.CountWordsWithPrefix(words, prefix)); // Output: 3

words = new string[] {"car", "cart", "cat"};
prefix = "ca";
Console.WriteLine(solution.CountWordsWithPrefix(words, prefix)); // Output: 3

words = new string[] {"dog", "deer", "dough"};
prefix = "do";
Console.WriteLine(solution.CountWordsWithPrefix(words, prefix)); // Output: 3
    

7. Conclusion

In this article, we explored how to solve string processing problems using the trie data structure. Tries are used for various purposes in many fields and are very useful for solving problems like string searches. We looked at the key ideas of tries along with their implementation in C#, and I hope that through various test cases, you can enhance your problem-solving skills.