Last active
May 6, 2024 07:30
-
-
Save aannenko/0eb5ca1775126c29335ef534c458384c to your computer and use it in GitHub Desktop.
Trie
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public sealed class Node | |
| { | |
| private readonly Dictionary<char, Node> _children = []; | |
| public IReadOnlyCollection<Node> Children => _children.Values; | |
| public string? Word { get; private set; } | |
| public Node GetOrAddChild(char letter, string? word = null) | |
| { | |
| if (!_children.TryGetValue(letter, out var node)) | |
| node = _children[letter] = new Node(); | |
| if (word is not null && node.Word is null) | |
| node.Word = word; | |
| return node; | |
| } | |
| public bool TryGetChild(char letter, [NotNullWhen(true)] out Node? node) => | |
| _children.TryGetValue(letter, out node); | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public static class NodeExtensions | |
| { | |
| public static void AddWord(this Node root, string word) | |
| { | |
| var node = root; | |
| for (int i = 0; i < word.Length; i++) | |
| node = node.GetOrAddChild(word[i], i == word.Length - 1 ? word : null); | |
| } | |
| public static bool TryGetChildByPrefix(this Node root, string prefix, [NotNullWhen(true)] out Node? node) | |
| { | |
| node = root; | |
| for (int i = 0; i < prefix.Length; i++) | |
| if (node is null || !node.TryGetChild(prefix[i], out node)) | |
| return false; | |
| return true; | |
| } | |
| public static IEnumerable<string> GetWords(this Node node) | |
| { | |
| if (node.Word is not null) | |
| yield return node.Word; | |
| foreach (var child in node.Children) | |
| foreach (var word in GetWords(child)) | |
| yield return word; | |
| } | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| using System.Diagnostics.CodeAnalysis; | |
| var words = new[] { "Ann", "Kasey", "Kate", "Jane", "Sandra" }; | |
| var root = new Node(); | |
| foreach (var word in words) | |
| root.AddWord(word); | |
| if (root.TryGetChildByPrefix("Ka", out var node)) | |
| foreach (var word in node.GetWords()) | |
| Console.WriteLine(word); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment