194 · 寻找单词(前缀和二分法)

链接LintCode 炼码题解双指针方法class Solution { public: /** * param str: the string * param dict: the dictionary * return: return words which are subsequences of the string */ vectorstring findWords(string str, vectorstring dict) { // write your code here. std::vectorstd::string result; for (auto q : dict) { if (valid(str, q)) { result.push_back(q); } } return result; } private: // 双指针方法 bool valid1(const std::string p, const std::string q) { if (p.size() 0) { return false; } int i 0; int j 0; while (i p.size() j q.size()) { if (p[i] q[j]) { i; j; } else { i; } } if (j q.size()) { return true; } return false; } };-二分法求解时间复杂度O(dict中所有字符的长度*log(str字符串长度))--将str字符对应的位置存在到ch2pos的hash表中--遍历dict中所有的元素与str进行对比--对比str和dict元素使用双指针进行对比--dict中对应字符在hash对应字符串中查找当前位置的地方class Solution { public: /** * param str: the string * param dict: the dictionary * return: return words which are subsequences of the string */ vectorstring findWords(string str, vectorstring dict) { // write your code here. std::unordered_mapchar, std::vectorint ch2pos; for (int i 0; i str.size(); i) { // 存储每个字符对应的位置 ch2pos[str[i]].push_back(i); } std::vectorstd::string result; // 判断是否为对应的单词 for (auto word : dict) { if (valid(ch2pos, str, word)) { // 追加结果 result.push_back(word); } } return result; } private: int find_left_index(const std::vectorint pos, int cur_pos) { int left 0; int right pos.size()-1; while (left 1 right) { int mid left (right-left)/2; if (pos[mid] cur_pos) { left mid; } else if (pos[mid] cur_pos) { right mid; } else { left mid; } } // 求得 cur_pos的位置 if (pos[left] cur_pos) { return pos[left]; } if (pos[right] cur_pos) { return pos[right]; } return -1; } bool valid(const std::unordered_mapchar, std::vectorint ch2pos, const std::string p, const std::string q) { if (p.size() 0) { return false; } int i 0; int j 0; while (i p.size() j q.size()) { if (p[i] q[j]) { i; j; } else { auto ite ch2pos.find(q[j]); // 如果当前字符不存在 if (ite ch2pos.end()) { return false; } // 查找当前位置该字符存在的位置 int pos find_left_index(ite-second, i); // 不存在该单词位置 if (pos -1) { return false; } /*if (p[pos] ! q[j]) { return false; }*/ // 更新移动下一个位置 i pos1; j; } } // 对比的单词到达末尾 if (j q.size()) { return true; } return false; } };class Solution { public: /** * param str: the string * param dict: the dictionary * return: return words which are subsequences of the string */ vectorstring findWords(string str, vectorstring dict) { // write your code here. std::vectorstd::string result; if (str.size() 0) { return result; } // table[i][j]当前这个字符i位置开始后面最接近的下字符j的位置是那个下标 std::vectorstd::vectorint table(str.size()1, std::vectorint(26, -1)); for (int i str.size() - 1; i 0; --i) { for (int j 0; j 26; j) { table[i][j] table[i1][j]; if (str[i] - a j) { // 如果是他自己就是它当前的位置 table[i][j] i; } } } for (auto q : dict) { if (valid(table, str, q)) { result.push_back(q); } } return result; } private: bool valid(const std::vectorstd::vectorint table, const std::string p, const std::string q) { if (p.size() 0) { return false; } int i 0; int j 0; while (i p.size() j q.size()) { /*if (p[i] q[j]) { i; j; } else {*/ // 获得字符q[j]的位置 int pos table[i][q[j]-a]; // 不存在这个位置 if (pos -1) { return false; } // 继续往后面查找 i pos 1; j; //} } if (j q.size()) { return true; } return false; } };class Solution { public: /** * param str: the string * param dict: the dictionary * return: return words which are subsequences of the string */ vectorstring findWords(string str, vectorstring dict) { // write your code here. int len str.size(); if (len 0) { return {}; } int dict_len dict.size(); if (dict_len 0) { return {}; } vectorvectorint nexts build(str); vectorstring result; for (auto str : dict) { if (is_same(nexts, len, str)) { result.push_back(str); } } return result; } bool is_same(vectorvectorint nexts, int len, const std::string str) { int i 0; int j 0; while (i len j str.size()) { int index str[j] - a; if (nexts[i][index] len) { //return false; break; } i nexts[i][index] 1; j; } // i在走道超过了可能j还没有走到最后 if (j str.size()) { return true; } return false; } vectorvectorint build(const std::string str) { int len str.size(); if (len 0) { return {}; } vectorvectorint nexts(len, vectorint(26, len)); for (int i str.size()-1; i 0; --i) { if (i ! str.size()-1) { nexts[i] nexts[i1]; } nexts[i][str[i]-a] i; /*for (char ch a; ch z; ch) { if (str[i] ch) { nexts[i][ch-a] i; } }*/ } return nexts; } };