补一个狗家店面跪经

周二面的，估计跪了，发上来攒点人品吧。
电话迟了5分多钟，上来就做题，没任何介绍。

“用过Eclipse吗？”
“用过”
“实现下Eclipse里的Camel-Case Search吧”


比如有一个Set里面有如下单词：FooBar, FootBall, FooToo, FiBa
Input a pattern, return all the

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ot;FiBa"
"FiB" should return "FiBa"


大概是要用Trie做，然而并没写出来，只写了个优化版的brute force

uranus23 发表于 2016-9-18 11:13
写错了，不用全出现，但出现的必须按顺序match前几个，不能跳

感觉就是和LC211类似办法，碰到小写字母就是往下走一层，碰到大写字母的时候在子树下面递归search。

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>&的
不过不影响正确性

谢谢楼主～bless
请问关于建立trie树的话，是不是一般的trie树呢还是有些改造呢, 大写和小写字母在carmel case的区别
比如FO可以match FoG类似这类吗 那Fo可以match FO吗，我的理解是大写必须都出现并且match上，小写可以match大写和小写，谢谢指教～
                    F
                  /  \
                o   
               /       i
              o      
            /   \      /
           T    B
           /    |
          o      a
          /      /  \
        o      r      l
                       \
                       l

感觉是分两情况：

1. Trie build 所有的word, 然后根据 search for prefix, 穷举这一条路径上的所有单词。
2. 把UPCASE 单独处理， 放到一个Map<String, List<String>> 里面。

其实我感觉都应该放到Map<String, List<String>> 中去， 这样子查询速度更快。

pinkdatura 发表于 2016-9-17 20:24
谢谢楼主～bless
请问关于建立trie树的话，是不是一般的trie树呢还是有些改造呢, 大写和小写字母在carmel  ...

“FO可以match FoG类似这类吗” 不可以
“Fo可以match FO吗” 不可以
“我的理解是大写必须都出现并且match上” Yes
“小写可以match大写和小写” 只能match小写

补充内容 (2016-9-17 22:12):
“我的理解是大写必须都出现并且match上” No..不必全出现，但出现过的要按顺序match

domofeng 发表于 2016-9-17 20:06
感觉是分两情况：

1. Trie build 所有的word, 然后根据 search for prefix, 穷举这一条路径上的所有单 ...

能给个第二种情况的例子吗？没太看懂

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

大写是必须都出现都match上吗？
第一个query是“F”的例子似乎并不符合这个原则啊..
或者说大写如果是部分必须是前几个，不能跳？

hxtang 发表于 2016-9-17 22:02
大写是必须都出现都match上吗？
第一个query是“F”的例子似乎并不符合这个原则啊..
或者说大写如果是 ...

写错了，不用全出现，但出现的必须按顺序match前几个，不能跳

hxtang 发表于 2016-9-17 22:30
感觉就是和LC211类似办法，碰到小写字母就是往下走一层，碰到大写字母的时候在子树下面递归search。

对，我想到了但没来得及写。。

http://www.geeksforgeeks.org/print-words-matching-pattern-camelcase-notation-dictonary/