0

I saw this pseudo-code on another stackoverflow question found here Split a string to a string of valid words using Dynamic Programming.

The problem is a dynamic programming question to see if an input string can be split into words from a dictionary.

The third line, means to set an array b of size [N+1] to all false values? I'm pretty sure about that. But what I am really not sure about is the fifth line. Is that a for-loop or what? I feel like pseudo-code saying 'for i in range' would only have 2 values. What is that line saying?

def try_to_split(doc):
   N = len(doc)
   b = [False] * (N + 1)
   b[N] = True
   for i in range(N - 1, -1, -1):
      for word starting at position i:
         if b[i + len(word)]:
            b[i] = True
            break
   return b
Community
  • 1
  • 1
Anthony J
  • 61
  • 1
  • 1
  • 5

1 Answers1

0

It's confusing syntax, and I'm pretty sure there's a mistake. It should be:

for i in range(N - 1, 0, -1) //0, not -1

which I believe means

for i from (N - 1) downto 0 //-1 was the step, like i-- or i -= 1

This makes sense with the algorithm, as it simply starts at the end of the string, and solves each trailing substring until it gets to the beginning. If b[0] is true at the end, then the input string can be split into words from the dictionary. for word starting at position i just checks all words in the dictionary to see if they start at that position.

If one wants to be able to reconstruct a solution, they can change b to an int array, initialize to 0s, and change the if to this:

if b[i + len(word)] != 0
    b[i] = i + len(word) //len(word) works too
    break
Millie Smith
  • 4,536
  • 2
  • 24
  • 60
  • Thank you. I believe it was a mistake too, and your revision makes the code make more sense. But what is the point of making b an int array, instead of a boolean array? – Anthony J Feb 27 '15 at 22:28
  • Suppose we set `b[i]` to `i + len(word)`. Then, if there is a solution, `b[i] != 0`. We can then find the actual solution by taking the word from `i = 0` to `i = b[0]`, and then repeat at `b[b[0]]` until we get to the end of the string. – Millie Smith Feb 27 '15 at 22:38
  • Sorry what do you mean by the "actual solution"? I don't see how using the method with the boolean array wouldn't work. – Anthony J Feb 27 '15 at 22:57
  • A boolean array would work, but say the string is "writtendoganimals". `b[0]` could be 7, `b[7]` could be 10, and `b[10]` could be `len(doc)`. In this way, you can know that the "actual solution" is "written" + "dog" + "animals". – Millie Smith Feb 27 '15 at 23:16
  • Oh ok, the int array would provide a way to 'retrieve' the actual strings. Going a further step, I see. Thank you. – Anthony J Feb 27 '15 at 23:18