2014-05-01 02:30
原题:
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.
题目:给定一个字母矩阵,给定一个单词,请判断从矩阵某一点出发,能否走出一条路径组成这个单词。每一步可以走8邻接的方向。
解法:这基本就是Leetcode的原题Word Search,DFS搞定。如果矩阵太大的话,可以用BFS防止递归过深造成的栈溢出,不过效率方面就更慢了。
代码:
1 // http://www.careercup.com/question?id=5890898499993600 2 class Solution { 3 public: 4 bool exist(vector> &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 > &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 here48 // letter mismatch here49 return false;50 }51 52 bool res;53 if (idx == word_len - 1) {54 // reach the end of word, success55 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 };