A structure that can group words with the same prefix.<\/li>\n<\/ul>\n\n A trie is typically structured as follows:\n <\/p>\n
\nclass TrieNode {\n Dictionary Children;\n bool IsEndOfWord;\n\n public TrieNode() {\n Children = new Dictionary();\n IsEndOfWord = false;\n }\n}\n \nclass Trie {\n private TrieNode root;\n\n public Trie() {\n root = new TrieNode();\n }\n\n public void Insert(string word) {\n TrieNode current = root;\n foreach (char c in word) {\n if (!current.Children.ContainsKey(c)) {\n current.Children[c] = new TrieNode();\n }\n current = current.Children[c];\n }\n current.IsEndOfWord = true;\n }\n\n public bool Search(string word) {\n TrieNode current = root;\n foreach (char c in word) {\n if (!current.Children.ContainsKey(c)) {\n return false;\n }\n current = current.Children[c];\n }\n return current.IsEndOfWord;\n }\n\n public bool StartsWith(string prefix) {\n TrieNode current = root;\n foreach (char c in prefix) {\n if (!current.Children.ContainsKey(c)) {\n return false;\n }\n current = current.Children[c];\n }\n return true;\n }\n}\n <\/char,><\/char,><\/code><\/pre>\n3. Problem Introduction<\/h2>\n
The problem we will cover in this lecture is as follows:<\/p>\n
Problem: Count the Number of Words with a Specific Prefix<\/h3>\n
\n Given a list of words and a specific prefix, write a function that returns the number of words that start with this prefix.
\n
\nInput:<\/strong><\/p>\n\n- Word list: [“apple”, “app”, “application”, “apricot”]<\/li>\n
- Prefix: “app”<\/li>\n<\/ul>\n
Output:<\/strong> 3 (The words “app”, “apple”, and “application” are in the word list.)\n <\/p>\n4. Problem-Solving Process<\/h2>\n
\n 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. <\/p>\n
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.
\n
\n 2. **Prefix Search**: Implement the logic to count the number of words that start with the specific prefix by performing a deep search.
\n
\n 3. **Return Result**: Return the count of words that start with the prefix.\n <\/p>\n
4.1 Code Implementation<\/h3>\n
Below is the complete code implemented in C#:<\/p>\n
\nclass Solution {\n public int CountWordsWithPrefix(string[] words, string prefix) {\n Trie trie = new Trie();\n \n \/\/ Insert all words into the trie\n foreach (string word in words) {\n trie.Insert(word);\n }\n \n \/\/ Counting the number of words that start with the prefix\n return CountWordsStartingWithPrefix(trie, prefix);\n }\n\n private int CountWordsStartingWithPrefix(Trie trie, string prefix) {\n TrieNode current = trie.Root;\n foreach (char c in prefix) {\n if (!current.Children.ContainsKey(c)) {\n return 0; \/\/ Return 0 if there are no words corresponding to the prefix\n }\n current = current.Children[c];\n }\n return CountAllWords(current); \/\/ Count all words below the prefix\n }\n\n private int CountAllWords(TrieNode node) {\n int count = 0;\n \n if (node.IsEndOfWord) {\n count++; \/\/ Increase word count if the current node is the end of a word\n }\n \n foreach (var child in node.Children) {\n count += CountAllWords(child.Value); \/\/ Recursively explore all child nodes\n }\n \n return count;\n }\n}\n <\/code><\/pre>\n5. Time Complexity Analysis<\/h3>\n
\n The time complexity for inserting a word into the trie is O(m), where m is the length of the word.
\n Searching for a prefix takes O(k) time (where k is the length of the prefix).
\n Thus, the overall time complexity is O(n * m + k), where n is the number of words.\n <\/p>\n
6. Test Cases<\/h2>\n
Here are a few test cases:<\/p>\n
\nstring[] words = {\"apple\", \"app\", \"application\", \"apricot\"};\nstring prefix = \"app\";\nSolution solution = new Solution();\nConsole.WriteLine(solution.CountWordsWithPrefix(words, prefix)); \/\/ Output: 3\n\nwords = new string[] {\"banana\", \"bandana\", \"band\"};\nprefix = \"ban\";\nConsole.WriteLine(solution.CountWordsWithPrefix(words, prefix)); \/\/ Output: 3\n\nwords = new string[] {\"car\", \"cart\", \"cat\"};\nprefix = \"ca\";\nConsole.WriteLine(solution.CountWordsWithPrefix(words, prefix)); \/\/ Output: 3\n\nwords = new string[] {\"dog\", \"deer\", \"dough\"};\nprefix = \"do\";\nConsole.WriteLine(solution.CountWordsWithPrefix(words, prefix)); \/\/ Output: 3\n <\/code><\/pre>\n7. Conclusion<\/h2>\n
\n 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.\n <\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
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 … \ub354 \ubcf4\uae30 “C# Coding Test Course, Try”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[90],"tags":[],"class_list":["post-33958","post","type-post","status-publish","format-standard","hentry","category-c-coding-test-tutorials"],"yoast_head":"\nC# Coding Test Course, Try - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/33958\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"C# Coding Test Course, Try - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"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 … \ub354 \ubcf4\uae30 "C# Coding Test Course, Try"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/33958\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:22:25+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T10:54:43+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"4\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/33958\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33958\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"C# Coding Test Course, Try\",\"datePublished\":\"2024-11-01T09:22:25+00:00\",\"dateModified\":\"2024-11-01T10:54:43+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33958\/\"},\"wordCount\":411,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"C# Coding Test Tutorials\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/33958\/\",\"url\":\"https:\/\/atmokpo.com\/w\/33958\/\",\"name\":\"C# Coding Test Course, Try - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:22:25+00:00\",\"dateModified\":\"2024-11-01T10:54:43+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33958\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/33958\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/33958\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"C# Coding Test Course, Try\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"C# Coding Test Course, Try - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/33958\/","og_locale":"ko_KR","og_type":"article","og_title":"C# Coding Test Course, Try - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"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 … \ub354 \ubcf4\uae30 \"C# Coding Test Course, Try\"","og_url":"https:\/\/atmokpo.com\/w\/33958\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:22:25+00:00","article_modified_time":"2024-11-01T10:54:43+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"4\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/33958\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/33958\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"C# Coding Test Course, Try","datePublished":"2024-11-01T09:22:25+00:00","dateModified":"2024-11-01T10:54:43+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/33958\/"},"wordCount":411,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["C# Coding Test Tutorials"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/33958\/","url":"https:\/\/atmokpo.com\/w\/33958\/","name":"C# Coding Test Course, Try - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:22:25+00:00","dateModified":"2024-11-01T10:54:43+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/33958\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/33958\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/33958\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"C# Coding Test Course, Try"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33958","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=33958"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33958\/revisions"}],"predecessor-version":[{"id":33959,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33958\/revisions\/33959"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=33958"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=33958"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=33958"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}