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;
}
} |
|
