h*****g 发帖数: 312 | 1 输入一个矩阵:
ABCE
SFCS
ADEE
和 一个string 比如 ABCCED
判断这个string 是否是矩阵的一个连续路径(可以上下左右移动,一次一格),矩阵
中用过的字母不能再用。
比如 ABCCED 可以。SEE 可以
但 ABCB 就不行 因为B 已被用过 不能往回走。 | i******r 发帖数: 793 | | g********e 发帖数: 118 | | i**********e 发帖数: 1145 | 4 经典 dfs,boggle 题。
用一个二维table来记录visited cell就可以了。 | m*****a 发帖数: 636 | 5 只能从top-left 开始吗
【在 h*****g 的大作中提到】 : 输入一个矩阵: : ABCE : SFCS : ADEE : 和 一个string 比如 ABCCED : 判断这个string 是否是矩阵的一个连续路径(可以上下左右移动,一次一格),矩阵 : 中用过的字母不能再用。 : 比如 ABCCED 可以。SEE 可以 : 但 ABCB 就不行 因为B 已被用过 不能往回走。
| h*****g 发帖数: 312 | 6 任意位置都可以开始
【在 m*****a 的大作中提到】 : 只能从top-left 开始吗
| i**********e 发帖数: 1145 | 7 不一定,可以从任何格子当起点。
【在 m*****a 的大作中提到】 : 只能从top-left 开始吗
| w**z 发帖数: 8232 | 8 要用Stack吧,每个点可以有多种可能的走法。是一个遍历 | i**********e 发帖数: 1145 | 9 请问 lz,SEE 可以代表可以 wrap around 对吧? | c*****e 发帖数: 737 | 10 好像蛮简单的么,就是一次取一个字母,看一下几种可能的情况保存一下,接着取下一
个,把走不通的结果踢出去,一直到走完。 | | | h*****g 发帖数: 312 | 11 从第二行 最后的一个S 开始,往下走,再往左走,就得到了。
【在 i**********e 的大作中提到】 : 请问 lz,SEE 可以代表可以 wrap around 对吧?
| i**********e 发帖数: 1145 | 12 恩,是的。我想多了 :)
【在 h*****g 的大作中提到】 : 从第二行 最后的一个S 开始,往下走,再往左走,就得到了。
| z*****n 发帖数: 447 | 13 思路并不很难,不过电面的时候直接coding写好也不容易,
Facebook电面就这一题,还是有几道coding题? | m*******r 发帖数: 339 | 14 我练练手,试着写了下:
public class StringPath {
public static boolean stringMatch(char[][] m, String s) {
StringBuffer sb = new StringBuffer();
boolean visited[][] = new boolean[m.length][m[0].length];
boolean found = false;
for (int i=0;i
for (int j=0;j
if (searchDFS(m, i, j, s, 0, visited, sb)) found = true;
}
}
return found;
}
public static boolean searchDFS(char[][] m, int x, int y, String s, int pos, boolean[][] v, StringBuffer sb) {
if (pos==s.length()) return true;
if (m[x][y]!=s.charAt(pos)) return false;
sb.append(m[x][y]);
v[x][y]=true;
boolean valid=false;
if (x>0 && !v[x-1][y] && searchDFS(m, x - 1, y, s, pos + 1, v, sb)) valid=true;
if (y>0 && !v[x][y-1]&& searchDFS(m, x, y - 1, s, pos + 1, v, sb)) valid=true;
if (x
if (y
sb.setLength(sb.length()-1);
v[x][y]=false;
return valid;
}
public static void main(String args[]) {
char[][] m = new char[][]{
{'A','B','C','E'},
{'S','F','C','S'},
{'A','D','E','E'}
};
System.out.println("ABCCED in matrix="+ stringMatch(m, "ABCCED"));
System.out.println("ABCB in matrix="+ stringMatch(m, "ABCB"));
System.out.println("SEE in matrix="+ stringMatch(m, "SEE"));
}
} | f********8 发帖数: 84 | 15 这个和我本周二intern oncampus的a家的题一模一样。。。
要简化的话可以加个function,比如提供一个字头,看字典里有没有这个字头开始的单
词 没有的话就不用继续走了。可以节约时间。
四个递归和我的思路一样。得到了面试官的认可。不过我却是把四个递归写进for loop
里面了。。。郁闷。
顺便我本科,楼主是? | p*****2 发帖数: 21240 | 16 如果要判断很多字符串的话,用trie更好吧?遍历一次建好trie,以后查找就容易了。 | z******t 发帖数: 59 | 17 基于回归算法做了一下,
解法放在博客里,
http://codercareer.blogspot.com/2012/02/no-34-string-path-in-ma
欢迎在博客评论中告知您的意见和建议。多谢:)
【在 h*****g 的大作中提到】 : 输入一个矩阵: : ABCE : SFCS : ADEE : 和 一个string 比如 ABCCED : 判断这个string 是否是矩阵的一个连续路径(可以上下左右移动,一次一格),矩阵 : 中用过的字母不能再用。 : 比如 ABCCED 可以。SEE 可以 : 但 ABCB 就不行 因为B 已被用过 不能往回走。
| f*******l 发帖数: 66 | 18 #include
#include
using namespace std;
bool isValid( char currentChar,int x, int y, int columnSize, int
rowSize,
char desiredChar, bitset <20> mybitset )
{
if(x < 0 || x > columnSize || y < 0 || y > rowSize )
{
return false ;
}
if ( mybitset[x*columnSize+y] == 1 )
{
return false;
}
if ( currentChar != desiredChar)
{
return false ;
}
return true ;
}
bool moveforward( int rowSize, int columnSize, char Array[][4], int x,
int y, char desired[], int stringSize, int currentLoc, bitset <20>
mybitset)
{
if ( currentLoc == (stringSize - 1)
&& desired[currentLoc] == Array[x][y])
{
return true ;
}
if ( currentLoc == (stringSize -1 ) && desired[currentLoc] !=
Array[x][y] )
{
return false ;
}
bool value = false;
mybitset.set(x*columnSize + y, 1);
if ( isValid( Array[x+1][y], x+1, y, columnSize, rowSize, desired[
currentLoc+1], mybitset ) == true )
{
value = moveforward(rowSize,columnSize, Array, x+1 , y,
desired,stringSize, currentLoc +1 , mybitset) ;
}
if ( value == false && isValid( Array[x-1][y], x-1, y,columnSize,
rowSize, desired[currentLoc+1], mybitset ) == true )
{
value = moveforward(rowSize, columnSize, Array, x-1 , y,
desired, stringSize, currentLoc +1 , mybitset) ;
}
if ( value == false && isValid( Array[x][y+1], x, y+1, columnSize,
rowSize, desired[currentLoc+1], mybitset ) == true )
{
value = moveforward(rowSize, columnSize, Array, x , y+1,
desired, stringSize, currentLoc +1 , mybitset) ;
}
if ( value == false && isValid( Array[x][y-1], x, y-1, columnSize,
rowSize, desired[currentLoc+1], mybitset ) == true )
{
value = moveforward(rowSize, columnSize, Array, x , y-1,
desired, stringSize, currentLoc +1 , mybitset) ;
}
if( value == false )
{
mybitset.set(x*columnSize + y, 0);
return false ;
}
else
{
return true ;
}
}
bool checkstring( char array[][4], int columnSize, int rowSize , char
desired[], int stringSize)
{
// search
for(int i = 0 ; i < rowSize ; i++)
for ( int j = 0 ; j < columnSize ; j++)
{
// set up initial state
bitset <20> visited(0) ;
if( array[i][j] == desired[0])
{
visited.set( i*columnSize + j, 1) ;
bool value = moveforward( rowSize, columnSize, array, i
, j, desired, stringSize, 0, visited) ;
if ( value == true)
{
return true ;
}
}
}
return false ;
}
【在 m*******r 的大作中提到】 : 我练练手,试着写了下: : public class StringPath { : public static boolean stringMatch(char[][] m, String s) { : StringBuffer sb = new StringBuffer(); : boolean visited[][] = new boolean[m.length][m[0].length]; : boolean found = false; : for (int i=0;i: for (int j=0;j: if (searchDFS(m, i, j, s, 0, visited, sb)) found = true; : }
| z******w 发帖数: 36 | 19 用dfs的方法实现了一下,dfs有些改动,需要记录当前栈内已经访问的节点,发现当前点和路
径不符立即返回false,否则递归处理相邻的元素。一旦发现路径走完立即返回true
-----------------------------
import java.util.HashSet;
import java.util.Set;
public class FindPath {
public boolean findPath(String[] m, String path) {
if (path.length() == 0) return true;
for (int i = 0; i < m.length; i ++) {
for (int j = 0; j < m[0].length(); j ++) {
Set set = new HashSet();
if (dfs(m, i, j, path, 0, set))
return true;
}
}
return false;
}
private boolean dfs(String[] m, int i, int j, String path, int k,
Set set) {
if (m[i].charAt(j) == path.charAt(k)) {
set.add(i+":"+j);
if (k == path.length() - 1) {
return true;
}
int[] x = new int[]{i-1, i+1, i, i};
int[] y = new int[]{j, j, j+1, j-1};
for (int n = 0; n < x.length; n ++) {
if (x[n] < 0 || x[n] >= m.length || y[n] < 0 ||
y[n] >= m[0].length()) {
continue;
} else {
if (set.contains(x[n]+":"+y[n])) continue;
set.add(x[n]+":"+y[n]);
if (dfs(m, x[n], y[n], path, k+1, set)) {
return true;
}
set.remove(x[n]+":"+y[n]);
}
}
}
return false;
}
} |
|