11 Chapter 11 Solutions

Solution to Challenge 1

You’ll implement allStrings as a stored property. Inside StringTrie, add the following new property:

final Set<String> _allStrings = {};
Set<String> get allStrings => _allStrings;

This property is a Set that will separately store all the strings represented by the code unit collections in the trie. Making allStrings a getter prevents the property from being tampered with from the outside.

Next, in the insert method, find the line current.isTerminating = true and add the following below it:

_allStrings.add(text);

In the remove function, find the line current.isTerminating = false and add the following just below that line:

_allStrings.remove(text);

This ensures that your string set will stay in sync with the trie.

Adding the count and isEmpty properties is straightforward now that you’re keeping track of all the strings:

int get length => _allStrings.length;

bool get isEmpty => _allStrings.isEmpty;

That’s it!

Note

Just because you can do something doesn’t mean you should. Now that you’re storing all of the strings in your trie separately as a set, you’ve lost the space complexity benefits that trie gave you.

Solution to Challenge 2

In StringTrie you only dealt with code unit collections. Now you have to generalize the task to handle any collection. Since you need to be able to loop through the elements of whatever collection you’re inserting, searching for, or removing, a generic trie should require any input to be iterable.

Create a new file called trie.dart and add the following class to it:

import 'trie_node.dart';

class Trie<E, T extends Iterable<E>> {
  TrieNode<E> root = TrieNode(key: null, parent: null);
}

T represents the iterable collections that you’ll add to the trie while E represents the type for the TrieNode key. For example, given a list of code units, E is int for the code unit while T is List<int> for the collection.

Now that you have the generic types set up, you can implement the insert method like so:

void insert(T collection) {
  var current = root;
  for (E element in collection) {
    current.children[element] ??= TrieNode(
      key: element,
      parent: current,
    );
    current = current.children[element]!;
  }
  current.isTerminating = true;
}

This is almost identical to your StringTrie implementation except that now you iterate through the more generic elements of type E in a collection of type T.

The process to update contains and remove are similar:

• Parameter inputs are T collection.
• Use for (E element in collection) to loop through the elements.

Try out your generic Trie by running the following in main:

import 'trie.dart';

void main() {
  final trie = Trie<int, List<int>>();
  trie.insert('cut'.codeUnits);
  trie.insert('cute'.codeUnits);
  if (trie.contains('cute'.codeUnits)) {
    print('cute is in the trie');
  }
  trie.remove('cut'.codeUnits);
  assert(!trie.contains('cut'.codeUnits));
}

Run that and you’ll see the following results:

cute is in the trie
cut has been removed

From the user’s perspective, the code above isn’t quite as concise as your StringTrie was. However, the advantage is that your new Trie can handle any iterable collection, not just the code units of strings.