ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:
Timer 00:00
WPM --
Score --
Acc --
Correct chars --

R: Implement Trie for Prefix Search

R

Goal -- WPM

Ready
Exercise Algorithm Area
1TrieNode <- R6Class("TrieNode",

2public = list(

3children = NULL,

4isEndOfWord = FALSE,

5initialize = function() {

6self$children <- list()

7self$isEndOfWord <- FALSE

8}

9)

10)

11

12Trie <- R6Class("Trie",

13public = list(

14root = NULL,

15initialize = function() {

16self$root <- TrieNode$new()

17},

18

19insert = function(word) {

20if (nchar(word) == 0) {

21# Handle empty string insertion if necessary, e.g., mark root as end of word

22# For this implementation, we'll ignore empty strings or treat them as invalid

23return(invisible(self))

24}

25

26node <- self$root

27for (i in 1:nchar(word)) {

28char <- substr(word, i, i)

29if (is.null(node$children[[char]])) {

30node$children[[char]] <- TrieNode$new()

31}

32node <- node$children[[char]]

33}

34node$isEndOfWord <- TRUE

35return(invisible(self))

36},

37

38search_prefix = function(prefix) {

39if (nchar(prefix) == 0) {

40# An empty prefix matches everything if we consider it valid

41# For this implementation, we'll return TRUE if the trie is not empty

42# or if the root is marked as end of word (for empty string insertion)

43return(!is.null(self$root) && self$root$isEndOfWord)

44}

45

46node <- self$root

47for (i in 1:nchar(prefix)) {

48char <- substr(prefix, i, i)

49if (is.null(node$children[[char]])) {

50return(FALSE) # Prefix not found

51}

52node <- node$children[[char]]

53}

54# If we reached the end of the prefix, it exists in the trie

55return(TRUE)

56},

57

58# Helper to find the node corresponding to the end of a prefix

59_find_node = function(prefix) {

60node <- self$root

61for (i in 1:nchar(prefix)) {

62char <- substr(prefix, i, i)

63if (is.null(node$children[[char]])) {

64return(NULL)

65}

66node <- node$children[[char]]

67}

68return(node)

69},

70

71# Function to list all words starting with a given prefix

72list_words_with_prefix = function(prefix) {

73prefix_node <- self$._find_node(prefix)

74if (is.null(prefix_node)) {

75return(character(0))

76}

77

78words <- character(0)

79

80# Recursive helper to traverse from the prefix node

81.traverse <- function(node, current_word) {

82if (node$isEndOfWord) {

83words <<- c(words, paste0(prefix, current_word))

84}

85

86for (char in names(node$children)) {

87child_node <- node$children[[char]]

88.traverse(child_node, paste0(current_word, char))

89}

90}

91

92.traverse(prefix_node, "")

93return(words)

94}

95)

96)

97

98# Example Usage:

99# trie <- Trie$new()

100# trie$insert("apple")

101# trie$insert("app")

102# trie$insert("apricot")

103# trie$search_prefix("app") # TRUE

104# trie$search_prefix("ban") # FALSE

105# trie$list_words_with_prefix("ap") # c("apple", "app", "apricot")
Algorithm description viewbox

R: Implement Trie for Prefix Search

Algorithm description:

This R code defines a Trie (prefix tree) data structure using the R6 object-oriented system. A Trie is a tree-like data structure used for efficient retrieval of keys in a dataset of strings. It's particularly useful for operations like prefix searching, auto-completion, and spell checking. The implementation includes methods for inserting words and searching for prefixes.

Algorithm explanation:

The Trie data structure provides efficient string operations. Each node in the Trie represents a character, and paths from the root to a node represent prefixes. The `insert` method traverses the Trie, creating new nodes for characters not yet present, and marks the end of a word. The `search_prefix` method checks if a given prefix exists by traversing the Trie. If the traversal completes successfully, the prefix exists. The time complexity for both insertion and prefix search is O(L), where L is the length of the word or prefix, as we visit at most L nodes. The space complexity is O(N * L_avg), where N is the number of words and L_avg is the average length of words, as each character in each word might create a new node. Edge cases handled include empty strings (ignored or specially handled) and attempting to search for a prefix that doesn't exist. The invariant is that any path from the root to a node corresponds to a valid prefix of at least one inserted word.

Pseudocode:

class TrieNode:
  children = map of char to TrieNode
  isEndOfWord = boolean

class Trie:
  root = TrieNode

  function initialize():
    root = new TrieNode()

  function insert(word):
    if word is empty:
      return
    node = root
    for each character in word:
      if character not in node.children:
        node.children[character] = new TrieNode()
      node = node.children[character]
    node.isEndOfWord = true

  function search_prefix(prefix):
    if prefix is empty:
      return true (or check if root is end of word)
    node = root
    for each character in prefix:
      if character not in node.children:
        return false
      node = node.children[character]
    return true