@tcdowney/

dpv-6-4

Python

No description

fork
loading
Files
  • main.py
main.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
from collections import defaultdict

full_sentence = "you are a bold one"
split_sentence = full_sentence.split(" ")
s = list("".join(split_sentence)) # e.g. 'youareaboldone'

n = len(s) + 1
t = [False] * n
next_word_idx = [0] * n

starter_words = {
  "it": True,
  "was": True,
  "the": True,
  "he": True,
  "best": True,
  "to": True,
  "of": True,
  "times": True,
  "time": True,
  "twas": True
}

d = defaultdict(bool, starter_words)

# Add in the words from our sentence
# to the dictionary
for word in split_sentence:
  d[word] = True

# Base case
t[0] = True

# Recurrence
for i in range(1, n):
  t[i] = False
  for j in range(1, i+1):
    # i and j correspond to our memoization array t
    # which contains an extra element to represent the
    # empty substring. We must adjust them to work with
    # the s character array.
    si = i - 1
    sj = j - 1

    substr = "".join(s[sj:si+1])

    if d[substr] and t[j-1]:
      t[i] = True
      next_word_idx[j-1] = i

print("The string s contains a valid sentence:")
print(t[n-1])

# Extract the words back out
prev = 0
words = []
for i in next_word_idx:
  if i != 0:
    word = s[prev:i]
    words.append("".join(word))
    prev = i

print("")
print("The words in the sentence are:")
print(words)