211. Search word wildcard

211_solution1_mixed.c

#include <stdbool.h>
#include <stdlib.h>

typedef struct WordDictionary {
  struct WordDictionary *children[26];
  bool isEnd;
} WordDictionary;

WordDictionary *wordDictionaryCreate() {
  return calloc(1, sizeof(WordDictionary));
}

void wordDictionaryAddWord(WordDictionary *obj, char *word) {
  WordDictionary *cur = obj;
  for (; *word; word++) {
    int i = *word - 'a';
    if (!cur->children[i])
      cur->children[i] = wordDictionaryCreate();
    cur = cur->children[i];
  }
  cur->isEnd = true;
}

static bool searchFrom(const WordDictionary *cur, const char *word) {
  for (; *word; word++) {
    if (*word != '.') {
      cur = cur->children[*word - 'a'];
      if (!cur)
        return false;
    } else {
      for (int i = 0; i < 26; i++) {
        if (cur->children[i] && searchFrom(cur->children[i], word + 1))
          return true;
      }
      return false;
    }
  }
  return cur->isEnd;
}

bool wordDictionarySearch(WordDictionary *obj, char *word) {
  return searchFrom(obj, word);
}

void wordDictionaryFree(WordDictionary *obj) {
  if (!obj)
    return;
  for (int i = 0; i < 26; i++)
    wordDictionaryFree(obj->children[i]);
  free(obj);
}

211_solution2_fullyrecursive.c

#include <stdbool.h>
#include <stdlib.h>

typedef struct WordDictionary {
  struct WordDictionary *children[26];
  bool isEnd;
} WordDictionary;

WordDictionary *wordDictionaryCreate() {
  return calloc(1, sizeof(WordDictionary));
}

void wordDictionaryAddWord(WordDictionary *obj, char *word) {
  WordDictionary *cur = obj;
  for (; *word; word++) {
    int i = *word - 'a';
    if (!cur->children[i])
      cur->children[i] = wordDictionaryCreate();
    cur = cur->children[i];
  }
  cur->isEnd = true;
}

static bool dfs(const WordDictionary *cur, const char *word) {
  if (!cur)
    return false;
  if (!*word)
    return cur->isEnd;

  if (*word != '.')
    return dfs(cur->children[*word - 'a'], word + 1);

  for (int i = 0; i < 26; i++)
    if (dfs(cur->children[i], word + 1))
      return true;
  return false;
}

bool wordDictionarySearch(WordDictionary *obj, char *word) {
  return dfs(obj, word);
}

void wordDictionaryFree(WordDictionary *obj) {
  if (!obj)
    return;
  for (int i = 0; i < 26; i++)
    wordDictionaryFree(obj->children[i]);
  free(obj);
}

211_solution1_mixed.cpp

#include <string>

using namespace std;

class WordDictionary {
  struct Node {
    Node *children[26] = {};
    bool is_end = false;
  };

  Node *root;

  bool searchFrom(const Node *cur, const string &word, int pos) const {
    for (int i = pos; i < (int)word.size(); i++) {
      char ch = word[i];
      if (ch != '.') {
        cur = cur->children[ch - 'a'];
        if (!cur)
          return false;
      } else {
        for (const Node *n : cur->children) {
          if (n && searchFrom(n, word, i + 1))
            return true;
        }
        return false;
      }
    }
    return cur->is_end;
  }

  void destroy(Node *n) {
    if (!n)
      return;
    for (Node *c : n->children)
      destroy(c);
    delete n;
  }

public:
  WordDictionary() { root = new Node(); }
  ~WordDictionary() { destroy(root); }

  void addWord(const string &word) {
    Node *cur = root;
    for (char ch : word) {
      int i = ch - 'a';
      if (!cur->children[i])
        cur->children[i] = new Node();
      cur = cur->children[i];
    }
    cur->is_end = true;
  }

  bool search(const string &word) const { return searchFrom(root, word, 0); }
};

211_solution2_fullyrecursive.cpp

#include <string>

using namespace std;

class WordDictionary {
  struct Node {
    Node *children[26] = {};
    bool is_end = false;
  };

  Node *root = new Node();

  bool dfs(const Node *cur, const string &word, int i) const {
    if (!cur)
      return false;
    if (i == (int)word.size())
      return cur->is_end;

    if (word[i] != '.')
      return dfs(cur->children[word[i] - 'a'], word, i + 1);

    for (const Node *child : cur->children)
      if (dfs(child, word, i + 1))
        return true;
    return false;
  }

  void destroy(Node *n) {
    if (!n)
      return;
    for (Node *c : n->children)
      destroy(c);
    delete n;
  }

public:
  ~WordDictionary() { destroy(root); }

  void addWord(const string &word) {
    Node *cur = root;
    for (char ch : word) {
      Node *&next = cur->children[ch - 'a'];
      if (!next)
        next = new Node();
      cur = next;
    }
    cur->is_end = true;
  }

  bool search(const string &word) const { return dfs(root, word, 0); }
};

211_solution1_mixed.go

package tries

type WordDictionary struct {
    children [26]*WordDictionary
    isEnd    bool
}

func Constructor() WordDictionary {
    return WordDictionary{}
}

func (d *WordDictionary) AddWord(word string) {
    cur := d
    for _, ch := range word {
        i := ch - 'a'
        if cur.children[i] == nil {
            cur.children[i] = &WordDictionary{}
        }
        cur = cur.children[i]
    }
    cur.isEnd = true
}

func (d *WordDictionary) Search(word string) bool {
    return d.searchFrom(word, 0)
}

func (d *WordDictionary) searchFrom(word string, pos int) bool {
    cur := d
    for i := pos; i < len(word); i++ {
        if word[i] != '.' {
            cur = cur.children[word[i]-'a']
            if cur == nil {
                return false
            }
            continue
        }
        for _, n := range cur.children {
            if n != nil && n.searchFrom(word, i+1) {
                return true
            }
        }
        return false
    }
    return cur.isEnd
}

211_solution2_fullyrecursive.go

package tries

type WordDictionary struct {
    children [26]*WordDictionary
    isEnd    bool
}

func Constructor() WordDictionary {
    return WordDictionary{}
}

func (d *WordDictionary) AddWord(word string) {
    cur := d
    for _, ch := range word {
        next := &cur.children[ch-'a']
        if *next == nil {
            *next = &WordDictionary{}
        }
        cur = *next
    }
    cur.isEnd = true
}

func (d *WordDictionary) Search(word string) bool {
    return dfs(d, word, 0)
}

func dfs(cur *WordDictionary, word string, i int) bool {
    if cur == nil {
        return false
    }
    if i == len(word) {
        return cur.isEnd
    }

    if word[i] != '.' {
        return dfs(cur.children[word[i]-'a'], word, i+1)
    }

    for _, child := range cur.children {
        if dfs(child, word, i+1) {
            return true
        }
    }
    return false
}

211_solution1_mixed.java

class WordDictionary {
    private static class Node {
        Node[] children = new Node[26];
        boolean isEnd;
    }

    private final Node root = new Node();

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

    public boolean search(String word) {
        return searchFrom(root, word, 0);
    }

    private boolean searchFrom(Node cur, String word, int pos) {
        for (int i = pos; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (ch != '.') {
                cur = cur.children[ch - 'a'];
                if (cur == null)
                    return false;
            } else {
                for (Node n : cur.children) {
                    if (n != null && searchFrom(n, word, i + 1))
                        return true;
                }
                return false;
            }
        }
        return cur.isEnd;
    }
}

211_solution2_fullyrecursive.java

class WordDictionary {
    private static class Node {
        Node[] children = new Node[26];
        boolean isEnd;
    }

    private final Node root = new Node();

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

    public boolean search(String word) {
        return dfs(root, word, 0);
    }

    private boolean dfs(Node cur, String word, int i) {
        if (cur == null)
            return false;
        if (i == word.length())
            return cur.isEnd;

        char ch = word.charAt(i);
        if (ch != '.')
            return dfs(cur.children[ch - 'a'], word, i + 1);

        for (Node child : cur.children)
            if (dfs(child, word, i + 1))
                return true;
        return false;
    }
}

211_solution1_mixed.js

class Node {
  constructor() {
    this.children = new Map();
    this.isEnd = false;
  }
}

class WordDictionary {
  constructor() {
    this.root = new Node();
  }

  addWord(word) {
    let cur = this.root;
    for (const ch of word) {
      if (!cur.children.has(ch)) cur.children.set(ch, new Node());
      cur = cur.children.get(ch);
    }
    cur.isEnd = true;
  }

  search(word) {
    return this.searchFrom(this.root, word, 0);
  }

  searchFrom(cur, word, pos) {
    for (let i = pos; i < word.length; i++) {
      const ch = word[i];
      if (ch !== ".") {
        cur = cur.children.get(ch);
        if (!cur) return false;
      } else {
        for (const n of cur.children.values()) {
          if (this.searchFrom(n, word, i + 1)) return true;
        }
        return false;
      }
    }
    return cur.isEnd;
  }
}

211_solution2_fullyrecursive.js

class Node {
  constructor() {
    this.children = new Map();
    this.isEnd = false;
  }
}

class WordDictionary {
  constructor() {
    this.root = new Node();
  }

  addWord(word) {
    let cur = this.root;
    for (const ch of word) {
      if (!cur.children.has(ch)) cur.children.set(ch, new Node());
      cur = cur.children.get(ch);
    }
    cur.isEnd = true;
  }

  search(word) {
    return this.dfs(this.root, word, 0);
  }

  dfs(cur, word, i) {
    if (!cur) return false;
    if (i === word.length) return cur.isEnd;

    if (word[i] !== ".") return this.dfs(cur.children.get(word[i]), word, i + 1);

    for (const child of cur.children.values())
      if (this.dfs(child, word, i + 1)) return true;
    return false;
  }
}

211_solution1_mixed.py

class Node:
    def __init__(self):
        self.children: dict[str, "Node"] = {}
        self.is_end = False


class WordDictionary:
    def __init__(self):
        self.root = Node()

    def addWord(self, word: str) -> None:
        cur = self.root
        for ch in word:
            cur = cur.children.setdefault(ch, Node())
        cur.is_end = True

    def search(self, word: str) -> bool:
        return self._search_from(self.root, word, 0)

    def _search_from(self, cur: Node, word: str, pos: int) -> bool:
        for i in range(pos, len(word)):
            ch = word[i]
            if ch != ".":
                cur = cur.children.get(ch)
                if not cur:
                    return False
            else:
                return any(
                    self._search_from(n, word, i + 1) for n in cur.children.values()
                )
        return cur.is_end

211_solution2_fullyrecursive.py

from typing import Optional


class Node:
    def __init__(self):
        self.children: dict[str, "Node"] = {}
        self.is_end = False


class WordDictionary:
    def __init__(self):
        self.root = Node()

    def addWord(self, word: str) -> None:
        cur = self.root
        for ch in word:
            cur = cur.children.setdefault(ch, Node())
        cur.is_end = True

    def search(self, word: str) -> bool:
        return self._dfs(self.root, word, 0)

    def _dfs(self, cur: Optional[Node], word: str, i: int) -> bool:
        if not cur:
            return False
        if i == len(word):
            return cur.is_end

        if word[i] != ".":
            return self._dfs(cur.children.get(word[i]), word, i + 1)

        return any(self._dfs(child, word, i + 1) for child in cur.children.values())

211_solution1_mixed.rs

#[derive(Default)]
struct WordDictionary {
    children: [Option<Box<WordDictionary>>; 26],
    is_end: bool,
}

impl WordDictionary {
    fn new() -> Self {
        Self::default()
    }

    fn add_word(&mut self, word: String) {
        let mut cur = self;
        for b in word.bytes() {
            cur = cur.children[(b - b'a') as usize].get_or_insert_with(Default::default);
        }
        cur.is_end = true;
    }

    fn search(&self, word: String) -> bool {
        self.search_from(word.as_bytes())
    }

    fn search_from(&self, word: &[u8]) -> bool {
        let mut cur = self;
        for (i, &b) in word.iter().enumerate() {
            if b != b'.' {
                match &cur.children[(b - b'a') as usize] {
                    Some(next) => cur = next,
                    None => return false,
                }
            } else {
                return cur
                    .children
                    .iter()
                    .flatten()
                    .any(|n| n.search_from(&word[i + 1..]));
            }
        }
        cur.is_end
    }
}

211_solution2_fullyrecursive.rs

#[derive(Default)]
struct WordDictionary {
    children: [Option<Box<WordDictionary>>; 26],
    is_end: bool,
}

impl WordDictionary {
    fn new() -> Self {
        Self::default()
    }

    fn add_word(&mut self, word: String) {
        let mut cur = self;
        for b in word.bytes() {
            cur = cur.children[(b - b'a') as usize].get_or_insert_with(Default::default);
        }
        cur.is_end = true;
    }

    fn search(&self, word: String) -> bool {
        Self::dfs(Some(self), word.as_bytes())
    }

    fn dfs(cur: Option<&WordDictionary>, word: &[u8]) -> bool {
        let Some(cur) = cur else { return false };
        let Some((&b, rest)) = word.split_first() else {
            return cur.is_end;
        };

        if b != b'.' {
            return Self::dfs(cur.children[(b - b'a') as usize].as_deref(), rest);
        }

        cur.children.iter().any(|child| Self::dfs(child.as_deref(), rest))
    }
}