l***4 发帖数: 1788 | 1 给一个list of string 和一个string s, 返回s是不是在list当中, s里可以包含一
个*代表一个任意字符。
想了一下应该用trie,但是感觉*处理起来比较棘手。
哪位大侠说下思路? | b**********5 发帖数: 7881 | | l***4 发帖数: 1788 | 3 是
【在 b**********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你这个*, 是只能match一个letter?
| b**********5 发帖数: 7881 | 4 看原题是说只有一个*, 然后还只能match一个letter, 不是Lee t code里的*, 那为
什么不能先看s 里有没有*, 没有就是一个hash set, 有就把那个* 变成a, b, c,d,.
..
【在 l***4 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是
| l***4 发帖数: 1788 | 5 可行!
要是面试官坚持让用trie呢?
,.
【在 b**********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 看原题是说只有一个*, 然后还只能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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 可行! : 要是面试官坚持让用trie呢? : : ,.
| l***4 发帖数: 1788 | 7 我明天按这个写一下
【在 b**********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你是说, 把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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给一个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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 将那个list of strings变成一个trie : 然后在这个trie里面查找s,search函数要写成如果当前s里面碰到了*,就在trie里面 : 做一层BFS。这题和那个在trie里面查找h3o (e.g., hello) pattern的词的写法很类似。
| l***4 发帖数: 1788 | 10 感谢分享
【在 b******i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 贴个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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感谢分享
| 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给一个list of string 和一个string s, 返回s是不是在list当中, s里可以包含一 : 个*代表一个任意字符。 : 想了一下应该用trie,但是感觉*处理起来比较棘手。 : 哪位大侠说下思路?
|
|