补一个狗家店面跪经

按照上面的思路，可以做一下改变
FooBar, FootBall, FooToo, FiBa 形成的trie 是这样的
             root
         F /
        (Foo, Fi)
    B /         T\   
   (FooBar     (FooToo)  
    FootBall
    FiBa)
search的时候，先把input 按照camel case 分成 “Fo” "Ba", 在每一层遍历startWith, 一直到找到。
其实就是把普通Trie一个字母一个字母匹配，变成一个单词一个单词匹配（startWith）。
话说电面就问这种难度，真是强人所难

补充内容 (2016-9-18 15:07):
不对，我说错了。如果是FoB，在叶子层没法扫描。。。可以每一层存成分开的单词组unordered_set，然后挨个遍历startWith

xytan123 发表于 2016-9-18 14:13
http://www.geeksforgeeks.org/print-words-matching-pattern-camelcase-notation-dictonary/

geeksforgeeks的这个要容易很多，就是把单词压缩成大写，然后对大写表示建trie就好了
但是这个题因为会出现部分小写所以会很麻烦，比如你11楼给的例子，如果query是FiT，那么应该什么都搜不到，所以不能把Foo和Fi放在一个结点里。

uranus23 发表于 2016-9-18 12:55
对，我想到了但没来得及写。。

如果是三四十分钟里要想还要从头到底写，不太可能写完。
不过如果来得及说思路的话，也许不一定会跪。G好像比较在乎思路，不太在乎code写完了没

给每个TrieNode加一条指向下一个可能的大写字母的指针就可以了

class TrieNode{
unordered_map<char,TrieNode*> nextChar;
unordered_map<char,TrieNode*> nextUpperChar;
string words;
};

有点疑惑这题为什么要分大小写呢？不是字符都要match吗

hxtang 发表于 2016-9-18 20:58
如果是三四十分钟里要想还要从头到底写，不太可能写完。
不过如果来得及说思路的话，也许不一定会跪。G ...

贴一个我写的实现。其实不难，核心就是两个*_recur函数，但是确实觉得电面那点时间连写带讲太不现实了，哪怕做过。

#include <iostream>
#include <cctype>
#include <vector>
#include <string>
using namespace std;

class CamelSearchEng {

    struct Node { //trie node
        //lazy impl. for children, ideally would only allocate space for alphabetical chars
        Node* children[256] = { nullptr };
        bool is_word = false;

        ~Node() {
            for (int k = 0; k < 256; ++k) delete children[k];
        }
    };

    Node* root;

public:
    //allocate trie
    CamelSearchEng(vector<string> words) {
        root = new Node;
        for (const string& word : words) {
            Node* t = root;
            for (char c : word) {
                if (t->children[c] == nullptr) t->children[c] = new Node;
                t = t->children[c];
            }
            t->is_word = true;
        }
    };

    // deallocate trie
    ~CamelSearchEng() {
        delete root;
    };

    // search CamelPattern
    vector<string> search(const string& pattern) const {
        vector<string> result;
        string word;
        search_recur(pattern, 0, root, word, result);
        return result;
    }

    void append_words_recur(Node* t, string& word, vector<string>& result) const {
        if (t->is_word) result.push_back(word);
        for (char c = 'a'; c <= 'z'; ++c) {
            if (t->children[c]) {
                word.push_back(c);
                append_words_recur(t->children[c], word, result);
                word.pop_back();
            }
        }
        for (char c = 'A'; c <= 'Z'; ++c) {
            if (t->children[c]) {
                word.push_back(c);
                append_words_recur(t->children[c], word, result);
                word.pop_back();
            }
        }
    }

    void search_recur(const string& pattern, int first, Node* t, string& word, vector<string>& result) const {
        size_t word_len = word.size();
        while (first < pattern.size() && islower(pattern[first]) && t) {
            t = t->children[pattern[first]];
            word.push_back(pattern[first]);
            ++first;
        }
        if (t == nullptr) {//no match
            ; //stop searching
        }
        else if (first == pattern.size()) { //found a matched prefix
            append_words_recur(t, word, result); //append all words under t
        }
        else { //pattern[first] is upper
            char c = pattern[first];
            for (int ch = 'a'; ch <= 'z'; ++ch) {
                if (t->children[ch]) search_recur(pattern, first, t->children[ch], word, result);
            }
            if (t->children[c]) {
                word.push_back(c);
                search_recur(pattern, first+1, t->children[c], word, result);
            }
        }

        //restore word for back tracing
        word.resize(word_len);
    }
};

void test(const CamelSearchEng& eng, const string& query) {
    cout << "query: " << query << endl;
    vector<string> result = eng.search(query);
    for (const string& str: result) cout << str << " ";
    cout << endl << endl;
}

int main() {
    vector<string> dictionary{"FooBar", "FootBall", "FooToo", "FiBa"};
    CamelSearchEng eng(dictionary);
    test(eng, "F");
    test(eng, "FB");
    test(eng, "FT");
    test(eng, "FoBa");
    test(eng, "FBa");
    test(eng, "FiB");
    return 0;   
}





补充内容 (2016-9-19 03:45):
写构造函数API的时候脑残了传了vector<string>，应该传const vector<string>&的
不过不影响正确性

感谢楼主分享。。。
电面给这个题感觉有点重口啊。。。。。

hxtang 发表于 2016-9-19 03:42
贴一个我写的实现。其实不难，核心就是两个*_recur函数，但是确实觉得电面那点时间连写带讲太不现实了， ...

挺难的。你的代码我读了好几遍...
难点在于，Trie是普通一个字母一个字母的结构，如果不完全match 了一段，就迎来下一个大写，怎样找到下一个大写的在trie里的位置。你的方法是遍历所有当前Trie Node 小写孩子，强迫前进。这样的话，如果是完全match了一段，比如，query('FooBaC') -->'FooBarCar',  其中'Foo'可以完全match , 我依旧要遍历所有第二个'o'下面的所有小写孩子 before starting to match 'B'。这个太难转过弯...

我想可不可以一个node包含一个group starting with the same Uppercase character, 然后这个group里面的成员再分别指向下一个camel case

补充内容 (2016-9-19 04:53):
class TrieNode {
    string word;
    unordered_map<char, vetor<TrieNode>>children;
}

补充内容 (2016-9-19 04:57):
                     root
                   /      
       (Foo,     Foot ,     Fi)   
        /                \       \
(Bar, Ball) (Too)   (Ball)   (Bar)

xytan123 发表于 2016-9-19 04:48
挺难的。你的代码我读了好几遍...
难点在于，Trie是普通一个字母一个字母的结构，如果不完全match 了一 ...

你说的这个想法我想过，我的主要顾虑是空间开销。vector<TrieNode>可能会非常大。

另外一个原因我没有信心在二三十分钟里写完这个数据结构。虽然search部分的实现逻辑变简单了（其实就差几行code），但构造部分很麻烦，如果TrieNode设计得不好，析构部分也会变复杂，容易出bug（例如你写的数据结构trie children和到下一个大写的shortcut没分开，delete会产生dangling pointer）。标准trie树如果状态好，还是有希望的。

如果面试官要求优化并且说有的是memory，我可能会提你说的这个idea。因为你指出的优化点是有意义的。

uranus23 发表于 2016-9-18 10:47
“FO可以match FoG类似这类吗” 不可以
“Fo可以match FO吗” 不可以
“我的理解是大写必须都出现并且m ...

谢谢楼主细心解答 关于小写，比如FiB能match FioBoo吗？还有FioB可以match FiiioooBoo, 但是肯定不能match FoiBoo或者FoBoo, FiBoo对吗？
就是比较像regular matching

大写*(0到n次)小写＋（1到n次）是吗？这道题关键在于改造trie树，好难啊，狗家最近怎么啦～