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 accessing parts of this content for free, with some sections shown as scrambled text.

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

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 accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now