find method

List<String> find(String prefix)

Finds all complete words in the trie matching the prefix.

Returns a list of all matches. If there are no matches, an empty list is returned.

Implementation

List<String> find(String prefix) {
  // Find the node of associated with the last character of the prefix.
  final lastCharacterNode = findPrefix(prefix, fromNode: _root);

  // The prefix does not exist in the tre.
  if (lastCharacterNode == null) {
    return [];
  }

  final stack = <_PartialMatch>[
    _PartialMatch(node: lastCharacterNode, partialWord: prefix),
  ];
  final foundWords = <String>[];

  while (stack.isNotEmpty) {
    final partialMatch = stack.removeLast();

    // The partial match node corresponds to an entire word.
    if (partialMatch.node.isEndOfWord) {
      foundWords.add(partialMatch.partialWord);
    }

    // Walk each of the child node of the partial match.
    for (final child in partialMatch.node.getChildren()) {
      stack.add(
        _PartialMatch(
          node: child,
          partialWord: "${partialMatch.partialWord}${child.key}",
        ),
      );
    }
  }

  return foundWords;
}