dropbox面经 （已挂T T)

1. bool match(string pattern, string data)
样例是：
pattern = 'abba',    data = 'red blue blue red'        true
pattern = 'abba',    data = 'red blue yellow red'     false
pattern = 'aaaa',    data = 'r

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

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

我用recursion+memoization，写完了面试官举了两个不能通过的case，对应地修改了一下，他看了一眼改完的版本说没什么问题。。。
大概是第二题木有bugfree的所以挂了= =。。。

思路应该差不多，楼主你是直接在纸上写的吗？这要是在纸上写，改来改去得乱成什么样啊

1. bool match(string pattern, string data, unordered_map<char, string> &lookup, unordered_set<string> &used) {
   
2.     if(pattern.size() == 0 && data.size() == 0)     return true;
   
3.     if(pattern.size() == 0 || data.size() == 0)     return false;
   
4. 
   
5.     unordered_map<char, string>::iterator it;
   
6.     it = lookup.find(pattern[0]);
   
7. 
   
8.     if(it != lookup.end()) {
   
9.         string word = it->second;
   
10.         if(data.size() < word.size() || data.substr(0, word.size()) != word) {
    
11.             return false;
    
12.         }else {
    
13.             return match2(pattern.substr(1), data.substr(word.size()), lookup, used);
    
14.         }   
    
15.     }else {
    
16.         for(int len = 1; len <= data.size(); len ++) {
    
17.             string new_word = data.substr(0, len);
    
18.             if(used.find(new_word) != used.end()) {
    
19.                 continue;                 
    
20.             }else {
    
21.                 used.insert(new_word);
    
22.                 lookup[pattern[0]] = new_word;
    
23.                 if(match2(pattern.substr(1), data.substr(new_word.size()), lookup, used)) {
    
24.                     return true;
    
25.                 }           
    
26.                 lookup.erase(pattern[0]);
    
27.                 used.erase(new_word);
    
28.             }   
    
29.         }   
    
30.     }   
    
31. 
    
32.     return false;
    
33. }
    

复制代码

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点击帖子下方的"好苗""分享""收藏"键，酌情给楼主加大米（系统不扣你自己的分）。
积分不够看不了帖子，请参考论坛导航里的"帮助"，"新手提纲"里有攒积分指南

第二题可以练一下DFS。C++ implementation。

void help(unordered_map<char, string> &info,
          unordered_set<string> &usedStr,
          const string &pattern, const string &data,
          int levelp, int leveld, bool &flag){

        int sizep = pattern.size();
        int sized = data.size();
        if (levelp == sizep || leveld == sized){
                flag = (levelp == sizep && leveld == sized);
                return;
        }

        string temp("");
        for (int i=levelp; i<sizep; i++){
                if (info.find(pattern[i]) == info.end()){
                        for (int j=leveld; j<sized; j++){
                                temp += data[j];
                                if (usedStr.find(temp) != usedStr.end()) continue;
                                usedStr.insert(temp);
                                info[pattern[i]] = temp;
                                help(info, usedStr, pattern, data, levelp+1, j+1, flag);
                                if (flag) return;
                                info.erase(pattern[i]);
                                usedStr.erase(temp);
                        }
                } else {
                        for (int j=leveld; j<sized; j++){
                                temp += data[j];
                                if (info[pattern[i]] != temp) continue;
                                help(info, usedStr, pattern, data, levelp+1, j+1, flag);
                                if (flag) return;
                        }
                }
        }
}


bool match(string pattern, string data){

        int p = pattern.size();
        if (p <= 1) return true;

        unordered_map<char, string> info; // store (char, string) relation
        unordered_set<string> usedStr; // store used string to avoid that different chars correponds to same string
        bool flag = false;
        help(info, usedStr, pattern, data, 0, 0, flag);

        return flag;
}


int main(){

        cout << match("abba", "redbluebluered") << endl;
        cout << match("abba", "redblueyellowred") << endl;
        cout << match("aaaa", "redredredred") << endl;
        cout << match("abba", "redredredred") << endl;

        return 0;
}


补充内容 (2014-10-8 09:11):
help function中第一个for loop是多余的，只要分析当前levelp那层就行

第二题你怎么做的

LZ是UIUC的啊？你是只面了周六一场还是周六周日两场？

kuyen 发表于 2014-10-8 09:00
第二题可以练一下DFS。C++ implementation。

void help(unordered_map &info,

dfs找字符串, 不如dfs插空格

为啥这么快就知道挂了？

readman 发表于 2014-10-8 07:45
第二题你怎么做的

lz代码又长又丑。。求指点...

1. bool helper(string pattern, string data, unordered_map<char, string>& dict, unordered_set<string>& exist_words) {
   
2.     if (pattern.size() == 1) {
   
3.         if (data == dict[pattern[0]]) {
   
4.             return true;
   
5.         } else {
   
6.             return false;
   
7.         }
   
8.     }
   
9.    
   
10.     char matched_pattern = pattern[0];
    
11.     bool pattern_exist = dict.find(matched_pattern) != dict.end();
    
12.    
    
13.     if (pattern_exist) {
    
14.         if (dict[matched_pattern] !=
    
15.             data.substr(0, dict[matched_pattern].size())) {
    
16.             return false;
    
17.         }
    
18.     }
    
19.    
    
20.     string sub_pattern = pattern.substr(1, pattern.size() + 1);
    
21.    
    
22.     for (int i = 1; i <= data.size(); ++i) {
    
23.         string matched_data = data.substr(0,i);
    
24.         if (!pattern_exist && exist_words.find(matched_data) != exist_words.end()) {
    
25.             continue;
    
26.         } else if (pattern_exist && dict[matched_pattern] != matched_data) {
    
27.             continue;
    
28.         }
    
29.         
    
30.         string sub_data = data.substr(i,data.size() + 1);
    
31.         
    
32.         if (!pattern_exist) {
    
33.             dict[matched_pattern] = matched_data;
    
34.             exist_words.insert(matched_data);
    
35.         }
    
36.         
    
37.         if (helper(sub_pattern, sub_data, dict, exist_words)) {
    
38.             return true;
    
39.         }
    
40.         
    
41.         if (!pattern_exist) {
    
42.             dict.erase(matched_pattern);
    
43.             exist_words.erase(matched_data);
    
44.         }
    
45.     }
    
46. }
    
47. 
    
48. bool match(string pattern, string data) {
    
49.     unordered_map<char, string> dict;
    
50.     unordered_set<string> exist_words;
    
51.     return helper(pattern, data, dict, exist_words);
    
52. }

复制代码

asdfg 发表于 2014-10-8 08:13
LZ是UIUC的啊？你是只面了周六一场还是周六周日两场？

周六就挂了。。没有收到通知去参加周日的。。。

tbu 发表于 2014-10-8 10:12
为啥这么快就知道挂了？

如果过了当天会收到通知参加第二天第二轮。。

yvetterowe 发表于 2014-10-7 20:31
周六就挂了。。没有收到通知去参加周日的。。。

我面了周日的到现在还没消息……也是出了个bug被举了反例才改对，看来有点不妙……