LZD_DeViL0902's blog

Strings are lethal for me!! Please help!!
By LZD_DeViL0902, history, 4 years ago, In English

Okay, so I again came up with a similar String question and I don't know how to approach these questions(Optimally), I will be thankful for the explanations if any..

Question Given a sentence string with no spaces in between, find the minimum number of spaces that can be there in the string so that all the generated words are present in a given dictionary. Example:

string: abcdef,,, No.of words in dictionary: 5,,, Dictionary: a bc def ab abc,,,

Answer: 1 ,,,,,, Explanation : By inserting 1 space as shown — 'abc def' we get 2 words abc and def which are valid words in the language Note: You could also split it as 'a bc def' But this would not be the case with minimum number of spaces.

I will be Thankful to the helping responses.

  • Vote: I like it
  • -14
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Dp + trie?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Aho–Corasick algorithm.

Form an array of indexes and after it there will be a easy linear solution

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Will it be linear? With input as "aaaaaaaaaaaaaa" and dictionary {"a", "aa", "aaa"...}

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

simply find the largest letter and put a space before it.

only the case when the largest letter is in front you need to check

→ Reply