How to find number of words in a phrase with spaces removed by checking v. dictionary

by

You can use Dynamic Programming for this task:

f(0) = 0
f(i) = MIN { f(i-j) + (Dictionary.contais(s.substring(i-j,i)?1:INFINITY } for each j=1,...,i

The above finds the number of words in your string, so the final answer is f(#characters)-1

The idea is to do an “exhaustive search” – for a given new character – try to connect it to a word, and recursively invoke on what’s left from the string.

This can be done pretty efficiently with DP techniques.

More Related Contents:

  1. How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag’s value]?
  2. Insertion sort stops working after million input
  3. How to find out how many bits are set (equal 1) in the product of two integers [closed]
  4. C++ – Find numbers between first and last negative numbers in Array
  5. Program stopped working, when tried to run
  6. How to replace all occurrences of a character in string?
  7. Image Processing: Algorithm Improvement for ‘Coca-Cola Can’ Recognition
  8. Rotating a point about another point (2D)
  9. Create Random Number Sequence with No Repeats
  10. Fast ceiling of an integer division in C / C++
  11. Getting the actual length of a UTF-8 encoded std::string?
  12. Search for a struct item in a vector by member data
  13. C++ Efficiently Calculating a Running Median [duplicate]
  14. Most efficient/elegant way to clip a number?
  15. The intersection of two sorted arrays
  16. Finding nearest point in an efficient way
  17. sine wave that slowly ramps up frequency from f1 to f2 for a given time
  18. Fast n choose k mod p for large n?
  19. Inverting a 4×4 matrix
  20. Print 2-D Array in clockwise expanding spiral from center
  21. Why would anyone use set instead of unordered_set?
  22. std::back_inserter for a std::set?
  23. How to rotate a N x N matrix by 90 degrees? [closed]
  24. Is it possible to map string to int faster than using hashmap?
  25. Is it possible to implement lock free map in C++
  26. stl ordering – strict weak ordering
  27. How to find Longest Common Substring using C++
  28. Generate N random numbers within a range with a constant sum
  29. Calculate mean and standard deviation from a vector of samples in C++ using Boost
  30. Checking if all elements of a vector are equal in C++

Leave a Comment