Search Pattern | tech::interview

Search Pattern | tech::interview

给一个dictionary, 再给一个set of coding string （g5, goo3, goog2, go2le………). return all string from dictionary that can be matched with the coding string. 要求尽量减少dictionary look up 次数。

因为给了一个字典，可能包含单词非常多，可以用trie来预处理。trie的代码请见Get Similar Words中的实现。下面只给出搜索函数。

int min_cover_mat(const vector<string>& map) {

if(map.empty() || map[0].empty()) return 0;

int rows = (int)map.size(), cols = (int)map[0].size();



auto lcm = [](int a, int b){

int mul = a * b;

for(int r = a % b; r ;){

a = b;

b = r;

r = a % b;

}

return mul / b;

};    

auto num_cover_substr_col = [&](int r) {

int next[cols+1], i = 0, j = -1;

next[0] = -1;

while(i < cols){

if(j == -1 || map[r][i] == map[r][j]){

++i, ++j;

next[i] = j;

} else j = next[j];

}

return i - next[i];

};

auto num_cover_substr_row = [&](int c) {

int next[rows+1], i = 0, j = -1;

next[0] = -1;

while(i < rows){

if(j == -1 || map[i][c] == map[j][c]){

++i, ++j;

next[i] = j;

} else j = next[j];

}

return i - next[i];

};



int r_nums = 1, c_nums = 1;



for(int r = 0; r < rows; r ++){

c_nums = lcm(c_nums, num_cover_substr_col(r));

if(c_nums > cols){

c_nums = cols;

break;

}

}

for(int c = 0; c < c_nums; c ++){

r_nums = lcm(r_nums, num_cover_substr_row(c));

if(r_nums > rows){

r_nums = rows;

break;

}

}

return r_nums * c_nums;

}

Read full article from Search Pattern | tech::interview