How to split a string into words. Ex: “stringintowords” -> “String Into Words”?

by

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.

More Related Contents:

  1. How to determine the longest increasing subsequence using dynamic programming?
  2. How does the Google “Did you mean?” Algorithm work? [closed]
  3. Subset Sum algorithm
  4. What is dynamic programming? [closed]
  5. Getting the submatrix with maximum sum?
  6. How to read values from numbers written as words?
  7. Is there an algorithm that tells the semantic similarity of two phrases
  8. Box stacking problem
  9. how to find longest palindromic subsequence?
  10. How to count integers between large A and B with a certain property?
  11. How to understand the dynamic programming solution in linear partitioning?
  12. Maximum Contiguous Subsequence Sum of At Least Length L
  13. 3-PARTITION problem
  14. Custom Weighted Scale [closed]
  15. Constant Amortized Time
  16. Expand a random range from 1–5 to 1–7
  17. What is pseudopolynomial time? How does it differ from polynomial time?
  18. True random number generator [closed]
  19. What is the difference between tree depth and height?
  20. What would cause an algorithm to have O(log n) complexity?
  21. Programming theory: Solve a maze
  22. Algorithm for finding numerical permutation given lexicographic index
  23. Fast Algorithm to Quickly Find the Range a Number Belongs to in a Set of Ranges?
  24. How to compute a 3D Morton number (interleave the bits of 3 ints)
  25. Calculating permutations in F#
  26. generate all partitions of a set [closed]
  27. RGB value base color name
  28. Variation on knapsack – minimum total value exceeding ‘W’
  29. Path generation for non-intersecting disc movement on a plane
  30. Calculating frames per second in a game

Leave a Comment