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.
Dp + trie?
Aho–Corasick algorithm.
Form an array of indexes and after it there will be a easy linear solution
Will it be linear? With input as "aaaaaaaaaaaaaa" and dictionary {"a", "aa", "aaa"...}
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