Geek asks and answers

Check if there is a line containing 2 words in the dictionary

I have an array of dictionary words and a random string like "twowords"

What is the fastest way to check if an entire string consists of dictionary words? therefore, "twojwords" will return false, and "twowords" will return true

I used binary search before but could not process two lines of words

(I use goal c)

+3
source share
3 answers

Here's a naive approach, but I don't know if there is a faster way.

for i1 from 0 to 6 do
  substring1 = string[0..i1];
  if (inDictionary(substring1)) {
    for i2 from i1+1 to 6 do
      substring2 = string[i1+1..i2];
      if (inDictionary(substring2)) {
        for i3 from i2+1 to 6 do 
... (up to i6)

To do this, you need to be able to form a substring of letters a to b of the string. For instance. if string = "thisisastring", then string[4..7] = "isas". You also need the inDictionary boolean function, which should do a binary search for a substring in a dictionary.

, . , 200000 , .

+3

, , , a la a BFS. , node, node, , . node , , node ( 1 ), node node. node , .

. , , , , , , . B) , n- n + 1th

+4

-, - - , ~ O (1) . , , 200 000

, , t-wowords, tw-owords, two-words, twow-ords .. .

, . :

bool checkWord(string word)
{
    if(length(word)==1)
        return isWordInDict(word);
    for each pair w1, w2 of word halfs
    {
        if(isWordInDict(w1) && checkWord(w2))
            return true;
    }
    return false;
}
+3
source

More articles:


All Articles