Chapters

Hide chapters

Data Structures & Algorithms in Dart

First Edition · Flutter · Dart 2.15 · VS Code 1.63

Section VI: Challenge Solutions

Section 6: 20 chapters
Show chapters Hide chapters

11. Chapter 11 Solutions
Written by Jonathan Sande & Kelvin Lau

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

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.

import 'trie_node.dart';

class Trie<E, T extends Iterable<E>> {
  TrieNode<E> root = TrieNode(key: null, parent: null);
}
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;
}
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));
}
cute is in the trie
cut has been removed
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now