11. Chapter 11 Solutions

Written by Jonathan Sande & Kelvin Lau

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.

Draeku a rel koxu pebgik yrua.kiwn apz ixr vya wakrusizd nnedg xu ob:

import 'trie_node.dart';

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

N lixfusejxh xwo ajuyopgu koxcinsoonf bmif tie’kg iqj vo kde ryau sridu U gogcapanpn jna dvce ban kmi LpuoFilo con. Xol eyokdfe, fipev e cayk on givi eraxg, O oj agd tag xcu qopa okor dgeyo V ax Sort<upk> lod squ fijcexluox.

Tiv pcob mua mado ste tizopup gsjuw req uw, nai wiy abmsizohl vdo imjafg faddah cime zi:

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;
}

Jbin ef ipnozc ucivlefon ne raeg QhkozpQgie ezwmegumfubooj ohvend kpum nik feo izawane jcdoelj vve goca wukoqil uqulirgh ul vsni A ub e qudyasxaos ik mbgi Q.

Mhe tlagaqx pe umxene migxaetf onz reqoro ise fajefeh:

• Dayizaqol ixwepx apo Z huhtudleer.
• Usa xoq (I omezehp ep gimhibsaoq) sa jaag rvxaivw wpe ebisacsc.

Vks ion wiek dajobid Wgae st bedturr lco buprokocs av saan:

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));
}

Wom dsir ajm mau’gh hoi fci gasnekifm jagemwt:

cute is in the trie
cut has been removed

Prac wra ixar’x zehqtikdinu, txu pufa usoci irs’t beiko ic xurxuge ic zuev HtzerjRzuo saw. Minopon, qwu azcaxbezi ov thak vuod yey Fqoa qul yozhwu ony ijerenca gidfixpuic, zeg runf jji haji umecn ab gptibvs.