Tries

class TrieNode:
    def __init__(self) -> None:
        # One slot per lowercase letter. None means no stored word continues that way.
        self.children: list[TrieNode | None] = [None] * 26
        self.is_word = False  # Whether a stored word ends exactly here.


class WordDictionary:
    """Stores words and finds them by pattern, where "." matches any one letter."""

    def __init__(self) -> None:
        self.root = TrieNode()

    def add_word(self, word: str) -> None:
        node = self.root
        for ch in word:
            i = ord(ch) - ord("a")
            if node.children[i] is None:
                node.children[i] = TrieNode()
            node = node.children[i]
        node.is_word = True

    def search(self, pattern: str) -> bool:
        return self._match(self.root, pattern, 0)

    def _match(self, node: TrieNode, pattern: str, i: int) -> bool:
        """Whether some stored word below `node` matches `pattern` from index `i` on."""
        # The pattern is used up, so it only matches if a word ends right here.
        if i == len(pattern):
            return node.is_word
        if pattern[i] == ".":
            # A dot can be any letter, so try every branch that exists.
            for branch in node.children:
                if branch is not None and self._match(branch, pattern, i + 1):
                    return True
            return False
        child = node.children[ord(pattern[i]) - ord("a")]
        return child is not None and self._match(child, pattern, i + 1)


if __name__ == "__main__":
    dictionary = WordDictionary()
    for word in ["bad", "dad", "mad"]:
        dictionary.add_word(word)
    print(dictionary.search("pad"))  # False
    print(dictionary.search("bad"))  # True
    print(dictionary.search(".ad"))  # True
    print(dictionary.search("b.."))  # True
    print(dictionary.search("b."))  # False

class TrieNode {
  // One slot per lowercase letter. null means no stored word continues that way.
  children: (TrieNode | null)[] = new Array<TrieNode | null>(26).fill(null);
  isWord = false; // Whether a stored word ends exactly here.
}

// Stores words and finds them by pattern, where "." matches any one letter.
export class WordDictionary {
  root = new TrieNode();

  addWord(word: string): void {
    let node = this.root;
    for (const ch of word) {
      const i = ch.charCodeAt(0) - "a".charCodeAt(0);
      node = node.children[i] ??= new TrieNode();
    }
    node.isWord = true;
  }

  search(pattern: string): boolean {
    return this.match(this.root, pattern, 0);
  }

  // Whether some stored word below `node` matches `pattern` from index `i` on.
  private match(node: TrieNode, pattern: string, i: number): boolean {
    // The pattern is used up, so it only matches if a word ends right here.
    if (i === pattern.length) return node.isWord;
    if (pattern[i] === ".") {
      // A dot can be any letter, so try every branch that exists.
      for (const branch of node.children) {
        if (branch !== null && this.match(branch, pattern, i + 1)) return true;
      }
      return false;
    }
    const child = node.children[pattern.charCodeAt(i) - "a".charCodeAt(0)];
    return child !== null && this.match(child, pattern, i + 1);
  }
}

const dictionary = new WordDictionary();
for (const word of ["bad", "dad", "mad"]) dictionary.addWord(word);
console.log(dictionary.search("pad")); // false
console.log(dictionary.search("bad")); // true
console.log(dictionary.search(".ad")); // true
console.log(dictionary.search("b..")); // true
console.log(dictionary.search("b.")); // false

package main

import "fmt"

// TrieNode is one node of a trie.
type TrieNode struct {
	// One slot per lowercase letter. nil means no stored word continues that way.
	children [26]*TrieNode
	isWord   bool // Whether a stored word ends exactly here.
}

// WordDictionary stores words and finds them by pattern, where "." matches
// any one letter.
type WordDictionary struct {
	root *TrieNode
}

func newWordDictionary() *WordDictionary {
	return &WordDictionary{root: &TrieNode{}}
}

func (d *WordDictionary) addWord(word string) {
	node := d.root
	for _, ch := range word {
		i := ch - 'a'
		if node.children[i] == nil {
			node.children[i] = &TrieNode{}
		}
		node = node.children[i]
	}
	node.isWord = true
}

func (d *WordDictionary) search(pattern string) bool {
	return d.match(d.root, pattern, 0)
}

// match reports whether some stored word below node matches pattern from
// index i on.
func (d *WordDictionary) match(node *TrieNode, pattern string, i int) bool {
	// The pattern is used up, so it only matches if a word ends right here.
	if i == len(pattern) {
		return node.isWord
	}
	if pattern[i] == '.' {
		// A dot can be any letter, so try every branch that exists.
		for _, branch := range node.children {
			if branch != nil && d.match(branch, pattern, i+1) {
				return true
			}
		}
		return false
	}
	child := node.children[pattern[i]-'a']
	return child != nil && d.match(child, pattern, i+1)
}

func main() {
	dictionary := newWordDictionary()
	for _, word := range []string{"bad", "dad", "mad"} {
		dictionary.addWord(word)
	}
	fmt.Println(dictionary.search("pad")) // false
	fmt.Println(dictionary.search("bad")) // true
	fmt.Println(dictionary.search(".ad")) // true
	fmt.Println(dictionary.search("b..")) // true
	fmt.Println(dictionary.search("b."))  // false
}

using System;

public class Solution
{
    public class TrieNode
    {
        // One slot per lowercase letter. null means no stored word continues that way.
        public TrieNode?[] Children = new TrieNode?[26];
        public bool IsWord; // Whether a stored word ends exactly here.
    }

    // Stores words and finds them by pattern, where "." matches any one letter.
    public class WordDictionary
    {
        readonly TrieNode root = new TrieNode();

        public void AddWord(string word)
        {
            var node = root;
            foreach (char ch in word)
            {
                int i = ch - 'a';
                node = node.Children[i] ??= new TrieNode();
            }
            node.IsWord = true;
        }

        public bool Search(string pattern) => Match(root, pattern, 0);

        // Whether some stored word below node matches pattern from index i on.
        bool Match(TrieNode node, string pattern, int i)
        {
            // The pattern is used up, so it only matches if a word ends right here.
            if (i == pattern.Length) return node.IsWord;
            if (pattern[i] == '.')
            {
                // A dot can be any letter, so try every branch that exists.
                foreach (var branch in node.Children)
                {
                    if (branch != null && Match(branch, pattern, i + 1)) return true;
                }
                return false;
            }
            var child = node.Children[pattern[i] - 'a'];
            return child != null && Match(child, pattern, i + 1);
        }
    }

    public static void Main()
    {
        var dictionary = new WordDictionary();
        foreach (var word in new[] { "bad", "dad", "mad" }) dictionary.AddWord(word);
        Console.WriteLine(dictionary.Search("pad")); // False
        Console.WriteLine(dictionary.Search("bad")); // True
        Console.WriteLine(dictionary.Search(".ad")); // True
        Console.WriteLine(dictionary.Search("b..")); // True
        Console.WriteLine(dictionary.Search("b.")); // False
    }
}

public class Solution {
    static class TrieNode {
        // One slot per lowercase letter. null means no stored word continues that way.
        TrieNode[] children = new TrieNode[26];
        boolean isWord; // Whether a stored word ends exactly here.
    }

    // Stores words and finds them by pattern, where "." matches any one letter.
    static class WordDictionary {
        private final TrieNode root = new TrieNode();

        void addWord(String word) {
            TrieNode node = root;
            for (char ch : word.toCharArray()) {
                int i = ch - 'a';
                if (node.children[i] == null) node.children[i] = new TrieNode();
                node = node.children[i];
            }
            node.isWord = true;
        }

        boolean search(String pattern) {
            return match(root, pattern, 0);
        }

        // Whether some stored word below node matches pattern from index i on.
        private boolean match(TrieNode node, String pattern, int i) {
            // The pattern is used up, so it only matches if a word ends right here.
            if (i == pattern.length()) return node.isWord;
            if (pattern.charAt(i) == '.') {
                // A dot can be any letter, so try every branch that exists.
                for (TrieNode branch : node.children) {
                    if (branch != null && match(branch, pattern, i + 1)) return true;
                }
                return false;
            }
            TrieNode child = node.children[pattern.charAt(i) - 'a'];
            return child != null && match(child, pattern, i + 1);
        }
    }

    public static void main(String[] args) {
        WordDictionary dictionary = new WordDictionary();
        for (String word : new String[] {"bad", "dad", "mad"}) dictionary.addWord(word);
        System.out.println(dictionary.search("pad")); // false
        System.out.println(dictionary.search("bad")); // true
        System.out.println(dictionary.search(".ad")); // true
        System.out.println(dictionary.search("b..")); // true
        System.out.println(dictionary.search("b.")); // false
    }
}

class TrieNode:
    def __init__(self) -> None:
        # One slot per lowercase letter. None means no stored word continues that way.
        self.children: list[TrieNode | None] = [None] * 26
        self.is_word = False  # Whether a stored root ends exactly here.


def insert(trie: TrieNode, word: str) -> None:
    """Adds `word` to the trie rooted at `trie`."""
    node = trie
    for ch in word:
        i = ord(ch) - ord("a")
        if node.children[i] is None:
            node.children[i] = TrieNode()
        node = node.children[i]
    node.is_word = True


def shortest_root(trie: TrieNode, word: str) -> str:
    """The shortest stored root that `word` starts with, or `word` itself if none does."""
    node = trie
    for i in range(len(word)):
        child = node.children[ord(word[i]) - ord("a")]
        if child is None:
            return word  # No root continues this way.
        # Prefixes come up shortest first, so the first root found is the answer.
        if child.is_word:
            return word[: i + 1]
        node = child
    return word  # The whole word is a path, but no root ends on it.


def replace_words(roots: list[str], sentence: str) -> str:
    """Replaces each word in `sentence` with the shortest root it starts with.
    Words that start with no root stay as they are."""
    trie = TrieNode()
    for root in roots:
        insert(trie, root)
    words = sentence.split(" ")
    for i in range(len(words)):
        words[i] = shortest_root(trie, words[i])
    return " ".join(words)


if __name__ == "__main__":
    print(replace_words(["cat", "bat", "rat"], "the cattle was rattled by the battery"))  # the cat was rat by the bat
    print(replace_words(["a", "b", "c"], "aadsfasf absbs bbab cadsfafs"))  # a a b c
    print(replace_words(["car", "ca", "dog"], "cart cab dot"))  # ca ca dot

class TrieNode {
  // One slot per lowercase letter. null means no stored word continues that way.
  children: (TrieNode | null)[] = new Array<TrieNode | null>(26).fill(null);
  isWord = false; // Whether a stored root ends exactly here.
}

// Adds `word` to the trie rooted at `trie`.
function insert(trie: TrieNode, word: string): void {
  let node = trie;
  for (const ch of word) {
    const i = ch.charCodeAt(0) - "a".charCodeAt(0);
    node = node.children[i] ??= new TrieNode();
  }
  node.isWord = true;
}

// The shortest stored root that `word` starts with, or `word` itself if none does.
function shortestRoot(trie: TrieNode, word: string): string {
  let node = trie;
  for (let i = 0; i < word.length; i++) {
    const child = node.children[word.charCodeAt(i) - "a".charCodeAt(0)];
    if (child === null) return word; // No root continues this way.
    // Prefixes come up shortest first, so the first root found is the answer.
    if (child.isWord) return word.slice(0, i + 1);
    node = child;
  }
  return word; // The whole word is a path, but no root ends on it.
}

// Replaces each word in `sentence` with the shortest root it starts with.
// Words that start with no root stay as they are.
export function replaceWords(roots: string[], sentence: string): string {
  const trie = new TrieNode();
  for (const root of roots) insert(trie, root);
  const words = sentence.split(" ");
  for (let i = 0; i < words.length; i++) words[i] = shortestRoot(trie, words[i]);
  return words.join(" ");
}

console.log(replaceWords(["cat", "bat", "rat"], "the cattle was rattled by the battery")); // the cat was rat by the bat
console.log(replaceWords(["a", "b", "c"], "aadsfasf absbs bbab cadsfafs")); // a a b c
console.log(replaceWords(["car", "ca", "dog"], "cart cab dot")); // ca ca dot

package main

import (
	"fmt"
	"strings"
)

// TrieNode is one node of a trie.
type TrieNode struct {
	// One slot per lowercase letter. nil means no stored word continues that way.
	children [26]*TrieNode
	isWord   bool // Whether a stored root ends exactly here.
}

// insert adds word to the trie rooted at trie.
func insert(trie *TrieNode, word string) {
	node := trie
	for _, ch := range word {
		i := ch - 'a'
		if node.children[i] == nil {
			node.children[i] = &TrieNode{}
		}
		node = node.children[i]
	}
	node.isWord = true
}

// shortestRoot returns the shortest stored root that word starts with, or
// word itself if none does.
func shortestRoot(trie *TrieNode, word string) string {
	node := trie
	for i := 0; i < len(word); i++ {
		child := node.children[word[i]-'a']
		if child == nil {
			return word // No root continues this way.
		}
		// Prefixes come up shortest first, so the first root found is the answer.
		if child.isWord {
			return word[:i+1]
		}
		node = child
	}
	return word // The whole word is a path, but no root ends on it.
}

// replaceWords replaces each word in sentence with the shortest root it
// starts with. Words that start with no root stay as they are.
func replaceWords(roots []string, sentence string) string {
	trie := &TrieNode{}
	for _, root := range roots {
		insert(trie, root)
	}
	words := strings.Split(sentence, " ")
	for i := range words {
		words[i] = shortestRoot(trie, words[i])
	}
	return strings.Join(words, " ")
}

func main() {
	fmt.Println(replaceWords([]string{"cat", "bat", "rat"}, "the cattle was rattled by the battery")) // the cat was rat by the bat
	fmt.Println(replaceWords([]string{"a", "b", "c"}, "aadsfasf absbs bbab cadsfafs"))                // a a b c
	fmt.Println(replaceWords([]string{"car", "ca", "dog"}, "cart cab dot"))                           // ca ca dot
}

using System;

public class Solution
{
    public class TrieNode
    {
        // One slot per lowercase letter. null means no stored word continues that way.
        public TrieNode?[] Children = new TrieNode?[26];
        public bool IsWord; // Whether a stored root ends exactly here.
    }

    // Adds word to the trie rooted at trie.
    static void Insert(TrieNode trie, string word)
    {
        var node = trie;
        foreach (char ch in word)
        {
            int i = ch - 'a';
            node = node.Children[i] ??= new TrieNode();
        }
        node.IsWord = true;
    }

    // The shortest stored root that word starts with, or word itself if none does.
    static string ShortestRoot(TrieNode trie, string word)
    {
        var node = trie;
        for (int i = 0; i < word.Length; i++)
        {
            var child = node.Children[word[i] - 'a'];
            if (child == null) return word; // No root continues this way.
            // Prefixes come up shortest first, so the first root found is the answer.
            if (child.IsWord) return word.Substring(0, i + 1);
            node = child;
        }
        return word; // The whole word is a path, but no root ends on it.
    }

    // Replaces each word in sentence with the shortest root it starts with.
    // Words that start with no root stay as they are.
    public static string ReplaceWords(string[] roots, string sentence)
    {
        var trie = new TrieNode();
        foreach (var root in roots) Insert(trie, root);
        var words = sentence.Split(' ');
        for (int i = 0; i < words.Length; i++) words[i] = ShortestRoot(trie, words[i]);
        return string.Join(" ", words);
    }

    public static void Main()
    {
        Console.WriteLine(ReplaceWords(new[] { "cat", "bat", "rat" }, "the cattle was rattled by the battery")); // the cat was rat by the bat
        Console.WriteLine(ReplaceWords(new[] { "a", "b", "c" }, "aadsfasf absbs bbab cadsfafs")); // a a b c
        Console.WriteLine(ReplaceWords(new[] { "car", "ca", "dog" }, "cart cab dot")); // ca ca dot
    }
}

public class Solution {
    static class TrieNode {
        // One slot per lowercase letter. null means no stored word continues that way.
        TrieNode[] children = new TrieNode[26];
        boolean isWord; // Whether a stored root ends exactly here.
    }

    // Adds word to the trie rooted at trie.
    static void insert(TrieNode trie, String word) {
        TrieNode node = trie;
        for (char ch : word.toCharArray()) {
            int i = ch - 'a';
            if (node.children[i] == null) node.children[i] = new TrieNode();
            node = node.children[i];
        }
        node.isWord = true;
    }

    // The shortest stored root that word starts with, or word itself if none does.
    static String shortestRoot(TrieNode trie, String word) {
        TrieNode node = trie;
        for (int i = 0; i < word.length(); i++) {
            TrieNode child = node.children[word.charAt(i) - 'a'];
            if (child == null) return word; // No root continues this way.
            // Prefixes come up shortest first, so the first root found is the answer.
            if (child.isWord) return word.substring(0, i + 1);
            node = child;
        }
        return word; // The whole word is a path, but no root ends on it.
    }

    // Replaces each word in sentence with the shortest root it starts with.
    // Words that start with no root stay as they are.
    static String replaceWords(String[] roots, String sentence) {
        TrieNode trie = new TrieNode();
        for (String root : roots) insert(trie, root);
        String[] words = sentence.split(" ");
        for (int i = 0; i < words.length; i++) words[i] = shortestRoot(trie, words[i]);
        return String.join(" ", words);
    }

    public static void main(String[] args) {
        System.out.println(replaceWords(new String[] {"cat", "bat", "rat"}, "the cattle was rattled by the battery")); // the cat was rat by the bat
        System.out.println(replaceWords(new String[] {"a", "b", "c"}, "aadsfasf absbs bbab cadsfafs")); // a a b c
        System.out.println(replaceWords(new String[] {"car", "ca", "dog"}, "cart cab dot")); // ca ca dot
    }
}