Careercup-Facebook面接問題-589089849993600
12449 ワード
2014-05-01 02:30
タイトルリンク
原題:
テーマ:アルファベットマトリクスを1つ、単語を1つ与えて、マトリクスのある点から、この単語を1つの経路で構成できるかどうかを判断してください.一歩ごとに8つの隣接する方向を歩くことができます.
解法:これは基本的にLeetcodeの原題Word Search、DFSでできます.行列が大きすぎると,BFSで再帰的深さによるスタックオーバーフローを防止できるが,効率面ではさらに遅くなる.
コード:
タイトルリンク
原題:
Given a matrix of letters and a word, check if the word is present in the matrix. E,g., suppose matrix is:
a b c d e f
z n a b c f
f g f a b c
and given word is fnz, it is present. However, gng is not since you would be repeating g twice.
You can move in all the 8 directions around an element.
テーマ:アルファベットマトリクスを1つ、単語を1つ与えて、マトリクスのある点から、この単語を1つの経路で構成できるかどうかを判断してください.一歩ごとに8つの隣接する方向を歩くことができます.
解法:これは基本的にLeetcodeの原題Word Search、DFSでできます.行列が大きすぎると,BFSで再帰的深さによるスタックオーバーフローを防止できるが,効率面ではさらに遅くなる.
コード:
1 // http://www.careercup.com/question?id=5890898499993600
2 class Solution {
3 public:
4 bool exist(vector<vector<char> > &board, string word) {
5 n = (int)board.size();
6 if (n == 0) {
7 return false;
8 }
9 m = (int)board[0].size();
10 word_len = (int)word.length();
11
12 if (word_len == 0) {
13 return true;
14 }
15
16 int i, j;
17 for (i = 0; i < n; ++i) {
18 for (j = 0; j < m; ++j) {
19 if(dfs(board, word, i, j, 0)) {
20 return true;
21 }
22 }
23 }
24 return false;
25 }
26 private:
27 int n, m;
28 int word_len;
29
30 bool dfs(vector<vector<char> > &board, string &word, int x, int y, int idx) {
31 static const int d[8][2] = {
32 {-1, -1},
33 {-1, 0},
34 {-1, +1},
35 { 0, -1},
36 { 0, +1},
37 {+1, -1},
38 {+1, 0},
39 {+1, +1}
40 };
41
42 if (x < 0 || x > n - 1 || y < 0 || y > m - 1) {
43 return false;
44 }
45
46 if (board[x][y] < 'A' || board[x][y] != word[idx]) {
47 // already searched here
48 // letter mismatch here
49 return false;
50 }
51
52 bool res;
53 if (idx == word_len - 1) {
54 // reach the end of word, success
55 return true;
56 }
57
58 for (int i = 0; i < 8; ++i) {
59 board[x][y] -= 'a';
60 res = dfs(board, word, x + d[i][0], y + d[i][1], idx + 1);
61 board[x][y] += 'a';
62 if (res) {
63 return true;
64 }
65 }
66 // all letters will be within [a-z], thus I marked a position as 'searched' by setting them to an invalid value.
67 // we have to restore the value when the DFS is done, so their values must still be distiguishable.
68 // therefore, I used an offset value of 'a'.
69 // this tricky way is to save the extra O(n * m) space needed as marker array.
70
71 return false;
72 }
73 };