2014雅虎校园招聘：二维字符数组查找Yahoo！（软件开发岗）

要求输入的单词的字符之间在数组里面是邻接关系

例如 ：输入二维字符矩阵如下：

A H E L

K M O L

H B W P

查找HELLOW明显可以找到，对应的坐标为(0,1)——>(0,2)——>(0,3)——>(1,3)——>(1,2)——>(2,2)，相当于一笔画成HELLOW！

本题采用枚举法实现。动态查找每一位的邻接是否满足条件，适当的剪枝是必要的！

JAVA源码如下(没有对输入数据进行合法性的检查！)：

package com;public class SearchWord {public static void main(String[] args) {String[] a = { "hello2rt", "orow -=!","xldpoiyx","uu!yuuzz" };System.out.println(isWord(a, "hello world!"));}public static boolean isWord(String[] matrix, String word) {boolean ok = false;for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[i].length(); j++) {ok = dfs(0, matrix, word, i, j);if (ok) break;}if (ok) break;}return ok;}public static boolean dfs(int index, String[] matrix, String word, int i,int j) {if (index >= word.length())return false;if (!(i >= 0 && i < matrix.length && j >= 0 && j < matrix[i].length()))return false;char cur = word.charAt(index);if (cur == matrix[i].charAt(j) && (index + 1) == word.length())return true;if (cur == matrix[i].charAt(j)) {if (dfs(index + 1, matrix, word, i - 1, j))return true;if (dfs(index + 1, matrix, word, i + 1, j))return true;if (dfs(index + 1, matrix, word, i, j - 1))return true;if (dfs(index + 1, matrix, word, i, j + 1))return true;}return false;}}

转载时请注明来源：http://blog.csdn.net/ccfeng2008

1楼leo52479小时前

今天这个笔试题不会，正好看看大牛怎么做的

Re: ccfeng200817分钟前

回复leo5247n代码没有对已经访问过的节点用二维数组（或其他方式）标记，会有点问题，一般情况还好，原因题目也没说的很清楚。