链接：LintCode 炼码

题解：

双指针方法：

class Solution {
public:/*** @param str: the string* @param dict: the dictionary* @return: return words which  are subsequences of the string*/vector<string> findWords(string &str, vector<string> &dict) {// write your code here.std::vector<std::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*/vector<string> findWords(string &str, vector<string> &dict) {// write your code here.std::unordered_map<char, std::vector<int>> ch2pos;for (int i = 0; i < str.size(); ++i) {// 存储每个字符对应的位置ch2pos[str[i]].push_back(i);}std::vector<std::string> result;// 判断是否为对应的单词for (auto& word : dict) {if (valid(ch2pos, str, word)) {// 追加结果result.push_back(word);}}return result;}
private:int find_left_index(const std::vector<int>& 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_map<char, std::vector<int>>& 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 = 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*/vector<string> findWords(string &str, vector<string> &dict) {// write your code here.std::vector<std::string> result;if (str.size() <= 0) {return result;}// table[i][j]当前这个字符i位置开始，后面最接近的下字符j的位置是那个下标std::vector<std::vector<int>> table(str.size()+1, std::vector<int>(26, -1));for (int i = str.size() - 1; i >= 0; --i) {for (int j = 0; j < 26; ++j) {table[i][j] = table[i+1][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::vector<std::vector<int>>& 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;}
};