l***4
发帖数: 1788 | 1 给一个list of string 和一个string s， 返回s是不是在list当中， s里可以包含一
个*代表一个任意字符。
想了一下应该用trie，但是感觉*处理起来比较棘手。
哪位大侠说下思路？ | b**********5
发帖数: 7881 | | l***4
发帖数: 1788 | 3 是
【在 b**********5 的大作中提到】
: 你这个*， 是只能match一个letter？
| b**********5
发帖数: 7881 | 4 看原题是说只有一个*， 然后还只能match一个letter， 不是Lee t code里的*， 那为
什么不能先看s 里有没有*， 没有就是一个hash set， 有就把那个* 变成a, b, c,d,.
..
【在 l***4 的大作中提到】
: 是
| l***4
发帖数: 1788 | 5 可行！
要是面试官坚持让用trie呢？
,.
【在 b**********5 的大作中提到】
: 看原题是说只有一个*， 然后还只能match一个letter， 不是Lee t code里的*， 那为
: 什么不能先看s 里有没有*， 没有就是一个hash set， 有就把那个* 变成a, b, c,d,.
: ..
| b**********5
发帖数: 7881 | 6 你是说， 把list of string 变成 prefix tree? 那不就是碰到*后， 每个node DFS？
【在 l***4 的大作中提到】
: 可行！
: 要是面试官坚持让用trie呢？
:
: ,.
| l***4
发帖数: 1788 | 7 我明天按这个写一下
【在 b**********5 的大作中提到】
: 你是说， 把list of string 变成 prefix tree? 那不就是碰到*后， 每个node DFS？
| b******i
发帖数: 914 | 8 将那个list of strings变成一个trie
然后在这个trie里面查找s，search函数要写成如果当前s里面碰到了*，就在trie里面
做一层BFS。这题和那个在trie里面查找h3o (e.g., hello) pattern的词的写法很类似。
【在 l***4 的大作中提到】
: 给一个list of string 和一个string s， 返回s是不是在list当中， s里可以包含一
: 个*代表一个任意字符。
: 想了一下应该用trie，但是感觉*处理起来比较棘手。
: 哪位大侠说下思路？
| b******i
发帖数: 914 | 9 贴个code，不过只test了几种case
/*
给一个list of string 和一个string s， 返回s是不是在list当中， s里可以包含一
个*代表一个任意字符。
*/
#include
#include
#include
using namespace std;
struct TrieNode {
TrieNode():is_word(false),children(26,nullptr) {}
bool is_word;
vector children;
};
class Solution {
public:
bool string_in_list(vector strings, string s) {
if(s.length() == 0 || strings.size() == 0)
return false;
// construct trie
TrieNode *root = new TrieNode();
for(auto str : strings)
trieInsert(root, str);
// search trie
return trieSearch(root, s, 0);
}
bool trieSearch(TrieNode *root, string s, int start) {
int n = s.length();
if(!root)
return false;
if(start == n)
return root->is_word;
char c = s[start];
if(c == '*') {
for(auto nextnode : root->children) {
if(trieSearch(nextnode, s, start+1))
return true;
}
return false;
}
return trieSearch(root->children[c-'a'], s, start+1);
}
void trieInsert(TrieNode *root, string s) {
int n = s.length();
if(n == 0)
return;
TrieNode *crawl = root;
for(int i = 0; i < n; i++) {
int idx = s[i] - 'a';
if(crawl->children[idx] == nullptr) {
crawl->children[idx] = new TrieNode();
}
crawl = crawl->children[idx];
}
crawl->is_word = true;
}
};
int main() {
Solution solution;
vector strings = {"google", "facebook", "linkedin"};
cout << solution.string_in_list(strings, "google") << endl;
cout << solution.string_in_list(strings, "goo*le") << endl;
cout << solution.string_in_list(strings, "**cebo**") << endl;
cout << solution.string_in_list(strings, "******") << endl;
cout << solution.string_in_list(strings, "googler") << endl;
cout << solution.string_in_list(strings, "***") << endl;
}
似。
【在 b******i 的大作中提到】
: 将那个list of strings变成一个trie
: 然后在这个trie里面查找s，search函数要写成如果当前s里面碰到了*，就在trie里面
: 做一层BFS。这题和那个在trie里面查找h3o (e.g., hello) pattern的词的写法很类似。
| l***4
发帖数: 1788 | 10 感谢分享
【在 b******i 的大作中提到】
: 贴个code，不过只test了几种case
: /*
: 给一个list of string 和一个string s， 返回s是不是在list当中， s里可以包含一
: 个*代表一个任意字符。
: */
: #include
: #include
: #include
: using namespace std;
: struct TrieNode {
| p*******9
发帖数: 2 | 11
拿到*的位置pos，然后把list中所有string的pos位置都换成*，最后hashmap
【在 l***4 的大作中提到】
: 感谢分享
| b***e
发帖数: 1419 | 12 You can build the trie in a smarter way to cut the cost per search.
Basically, when you index a string s of length n, instead of indexing itself
, you index n+1 strings: the original string and n other strings with the
character at each position missing. For instance, to index “abc”, you
index all of the following:
“abc”
“bc”
“ac”
“ab"
The overall index cost could be increased to O(N*k) in the worst case, where
N is the total number of characters occurring in all the strings, and k is
the average length of the strings. But when querying, you just need to do a
straightforward search by skipping the “*” that is encountered, if at all.
【在 l***4 的大作中提到】
: 给一个list of string 和一个string s， 返回s是不是在list当中， s里可以包含一
: 个*代表一个任意字符。
: 想了一下应该用trie，但是感觉*处理起来比较棘手。
: 哪位大侠说下思路？
|
|
