trie - OpenGenus IQ: Learn Computer Science

All Valid Word Breaks of a Sentence 【O(2^N) time complexity】

We are given with a valid sentence without any spaces and we are given with a dictionary of words. We need to print all the possible ways to break the sentence so that all the breaked words belongs to the dictionary.

data structure

Y fast trie

Y-fast trie is a data structure used to store integers from a bounded domain. It has two data structures X fast trie and balanced binary search tree with the change being we operate on representative values r in X-fast tries, and the leaf nodes point to balanced binary search trees instead of values

data structure

X-fast trie

X-fast trie is a data structure used to store integers from a bounded domain. It is a bitwise trie, i.e. a binary tree where each subtree stores values having binary representations with common prefix. It is a trie of hash tables and supports successor and predecessor operations in log log U time

data structure

Trie data structure

A trie (digital tree, radix tree, prefix tree) is a kind of an ordered search tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Worst case search time complexity is Θ(key_length) and trie is widely used in real life applications

data structure

Ternary Search Trees

Ternary Search Tree is a special type of trie data structure and is widely used as an low memory alternative to trie in a vast range of applications like spell check and near neighbor searching. The average case time complexity is O(log N) for look-up, insertion and deletion operation.