Clever Geek Handbook

What is the difficulty of creating a lexicographic tree

What is the difficulty in creating a lexicographic tree?

+2


source to share


4 answers


If you create a tree



+2


source


The appropriate data structure for this is probably a sorted list. In this case it becomes a half-and-half search problem, so O (log n).



+1


source


As Gabe mentioned, Trie is a good solution, but it is a little difficult to implement dictionaries with a lot of words. If O (n log n) algorithm works for you, you can solve this problem with binary search. Here's the code written in C:

char dict [n] [m]; // where n is number of words in dictionary and
                 // m is maximum possible length of word
char word [m]; // it your word

int l = -1, r = n;
while (l + 1 <r) {
  int k = (l + r) / 2;
  if (strcmp (dict [k], word) <0) l = k;
  else r = k;
}

int len ​​= strlen (word);
l ++; // first word index with greater or equal prefix then word is l + 1
bool matches = (strlen (word [l])> = len);
for (int i = 0; i <len && matches; i ++) {
  if (word [i]! = dict [l] [i]) {
    matches = 0;
  }
}

if (matches) {
  printf ("given word is prefix of% dth word.", l);
} else {
  printf ("given word isn't in dictinary.");
}
0


source


just starts with a simple loop and checks if each word starts with anything.

in almost every language there is a build function to check if one line starts with another.

complexity is O (log n) and n is the number of words in the dictionary.

-1


source






More articles:


All Articles