首页 > 代码库 > 《Cracking the Coding Interview》——第18章:难题——题目7
《Cracking the Coding Interview》——第18章:难题——题目7
2014-04-29 03:05
题目:给定一个词典,其中某些词可能能够通过词典里其他的词拼接而成。找出这样的组合词里最长的一个。
解法:Leetcode上有Word Break这道题,和这题基本思路一致。
代码:
1 // 18.7 Given a list of words, find out the longest word made of other words in the list. 2 #include <iostream> 3 #include <string> 4 #include <unordered_set> 5 #include <vector> 6 using namespace std; 7 8 class Solution { 9 public: 10 string longestBreakableWord(unordered_set<string> &dict) { 11 unordered_set<string>::const_iterator usit; 12 string res = ""; 13 14 for (usit = dict.begin(); usit != dict.end(); ++usit) { 15 if (wordBreak(*usit, dict) && usit->length() > res.length()) { 16 res = *usit; 17 } 18 } 19 20 return res; 21 } 22 private: 23 bool wordBreak(string s, unordered_set<string> &dict) { 24 int n; 25 int i, j; 26 string str; 27 vector<int> dp; 28 29 n = (int)s.length(); 30 if (n == 0 || dict.empty()) { 31 return false; 32 } 33 dp.resize(n); 34 for (i = 0; i < n; ++i) { 35 str = s.substr(0, i + 1); 36 if (dict.find(str) != dict.end()) { 37 dp[i] = 1; 38 } else { 39 for (j = 0; j < i; ++j) { 40 if (dp[j] && dict.find(s.substr(j + 1, i - j)) != dict.end()) { 41 dp[i] = 1; 42 break; 43 } 44 } 45 if (j == i) { 46 dp[i] = 0; 47 } 48 } 49 } 50 51 i = dp[n - 1]; 52 dp.clear(); 53 return i == 1; 54 } 55 }; 56 57 int main() 58 { 59 unordered_set<string> dict; 60 string s; 61 Solution sol; 62 int i, n; 63 64 while (cin >> n && n > 0) { 65 for (i = 0; i < n; ++i) { 66 cin >> s; 67 dict.insert(s); 68 } 69 70 cout << sol.longestBreakableWord(dict) << endl; 71 } 72 73 return 0; 74 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。