Word break

Questions 1 to 5 of 7

1. 1. Predict the output of this program. It prints the lookup counts of two versions. ``cpp #include <algorithm> #include <cstddef> #include <iostream> #include <string> #include <unordered_set> #include <utility> #include <vector> std::pair<bool, std::size_t> wordBreakAllSplits(const std::string& s, const std::vector<std::string>& words) { std::unordered_set<std::string> dict(words.begin(), words.end()); const std::size_t n = s.size(); std::vector<bool> ok(n + 1, false); ok[0] = true; std::size_t lookups = 0; for (std::size_t i = 1; i <= n; ++i) { for (std::size_t j = 0; j < i; ++j) { if (!ok[j]) continue; ++lookups; if (dict.contains(s.substr(j, i - j))) { ok[i] = true; break; } } } return {ok[n], lookups}; } std::pair<bool, std::size_t> wordBreakMaxLen(const std::string& s, const std::vector<std::string>& words) { std::unordered_set<std::string> dict(words.begin(), words.end()); std::size_t maxLen = 0; for (const auto& w : words) maxLen = std::max(maxLen, w.size()); const std::size_t n = s.size(); std::vector<bool> ok(n + 1, false); ok[0] = true; std::size_t lookups = 0; for (std::size_t i = 1; i <= n; ++i) { const std::size_t lowest = i > maxLen ? i - maxLen : 0; for (std::size_t j = lowest; j < i; ++j) { if (!ok[j]) continue; ++lookups; if (dict.contains(s.substr(j, i - j))) { ok[i] = true; break; } } } return {ok[n], lookups}; } int main() { auto a = wordBreakAllSplits("aa", {"a"}); auto m = wordBreakMaxLen("aa", {"a"}); std::cout << a.second << ' ' << m.second << '\n'; } ``

   2 22 33 23 3
2. 2. Predict the output of this program. It prints the answer and the lookup count. ``cpp #include <algorithm> #include <cstddef> #include <iostream> #include <string> #include <unordered_set> #include <utility> #include <vector> std::pair<bool, std::size_t> wordBreakAllSplits(const std::string& s, const std::vector<std::string>& words) { std::unordered_set<std::string> dict(words.begin(), words.end()); const std::size_t n = s.size(); std::vector<bool> ok(n + 1, false); ok[0] = true; std::size_t lookups = 0; for (std::size_t i = 1; i <= n; ++i) { for (std::size_t j = 0; j < i; ++j) { if (!ok[j]) continue; ++lookups; if (dict.contains(s.substr(j, i - j))) { ok[i] = true; break; } } } return {ok[n], lookups}; } int main() { auto r = wordBreakAllSplits("abcd", {"ab", "cd", "abc"}); std::cout << std::boolalpha << r.first << ' ' << r.second << '\n'; } ``

   true 4true 5false 5true 3
3. 3. The dictionary is {cat, cats, and, sand, dog}, so the longest word has 4 letters. In wordBreakMaxLen, what is the earliest start j that is checked when i = 10?

   0467
4. 4. Which statements about the word break table are true? Pick all that apply.

   Pick every answer that is true.

   ok[0] must be true, because the empty prefix splits into zero piecesStarting ok[0] as false still gives yes for the word cat with the dictionary {cat}The expression i - maxLen on std::size_t can wrap below zero, so the code guards itCalling substr with a start equal to the size of the string throws an exception
5. 5. Which sentence about the trie in the lesson is true?

   Each node can have up to 26 children, one for each letter a to z, and a node is marked when a complete word ends thereEach node stores the whole word it spells, so the trie holds a copy of every wordWords that share a start, such as cat and cats, are stored twice so that each walk can stop earlyThe walk copies each substring of s before it checks the trie