What is the right way to split a string into words ? (string doesn't contain any spaces or punctuation marks)
For example: "stringintowords" -> "String Into Words"
Could you please advise what algorithm should be used here ?
! Update: For those who think this question is just for curiosity. This algorithm could be used to camеlcase domain names ("sportandfishing .com" -> "SportAndFishing .com") and this algo is currently used by aboutus dot org to do this conversion dynamically.
Let's assume that you have a function isWord(w)
, which checks if w
is a word using a dictionary. Let's for simplicity also assume for now that you only want to know whether for some word w
such a splitting is possible. This can be easily done with dynamic programming.
Let S[1..length(w)]
be a table with Boolean entries. S[i]
is true if the word w[1..i]
can be split. Then set S[1] = isWord(w[1])
and for i=2
to length(w)
calculate
S[i] = (isWord[w[1..i] or for any j in {2..i}: S[j-1] and isWord[j..i]).
This takes O(length(w)^2) time, if dictionary queries are constant time. To actually find the splitting, just store the winning split in each S[i] that is set to true. This can also be adapted to enumerate all solution by storing all such splits.