《Cracking the Coding Interview》——第17章：普通题——题目14

 1 // 17.14 Given a dictionary of words, and a long string. You may find a way to cut the string into words, where some of them may or may not be in the dictionary.
 2 // Dynamic programming is a good thing, but trades space in for time.
 3 #include <iostream>
 4 #include <string>
 5 #include <unordered_set>
 6 #include <vector>
 7 using namespace std;
 8 
 9 int main()
10 {
11     string data;
12     unordered_set<string> dict;
13     vector<vector<bool> > contains;
14     vector<int> dp;
15     int i, j;
16     string s;
17     int n;
18     int tmp;
19     
20     while (cin >> data && data != "") {
21         cin >> n;
22         for (i = 0; i < n; ++i) {
23             cin >> s;
24             dict.insert(s);
25         }
26         n = (int)data.length();
27         
28         contains.resize(n);
29         for (i = 0; i < n; ++i) {
30             contains[i].resize(n);
31         }
32         for (i = 0; i < n; ++i) {
33             s = "";
34             for (j = i; j < n; ++j) {
35                 s.push_back(data[j]);
36                 contains[i][j] = (dict.find(s) != dict.end());
37             }
38         }
39         
40         dp.resize(n);
41         for (i = 0; i < n; ++i) {
42             dp[i] = contains[0][i] ? 0 : i + 1;
43             for (j = 0; j < i; ++j) {
44                 tmp = dp[j] + (contains[j + 1][i] ? 0 : i - j);
45                 dp[i] = dp[i] < tmp ? dp[i] : tmp;
46             }
47         }
48         
49         printf("%d\n", dp[n - 1]);
50         
51         for (i = 0; i < n; ++i) {
52             contains[i].clear();
53         }
54         contains.clear();
55         dp.clear();
56         dict.clear();
57     }
58     
59     return 0;
60 }