Amazon Intern Phone Interview Feb 4th 2pm PST

三塘木 发表于 2016-2-10 02:12
第二题lc好像有原题吧？只不过lc是四方向的貌似

嗯，后来别人告诉我查了一下的确是，似乎是一个word search还是啥的

ntgd1102 发表于 2016-2-9 17:03
楼主， 这个题要用的BFS的话，你怎么标记啊visted的啊？

我就是非常鱼唇的开了一个数组……

ntgd1102 发表于 2016-2-9 17:03
楼主， 这个题要用的BFS的话，你怎么标记啊visted的啊？

我就是非常鱼唇的开了一个数组……

我觉得直接DFS就可以了吧，不需要额外空间，每次用过的matrix位置改为一个其余字符

其实这个题用BFS的话，就自己建一个costume class， 里面放个LinkedHashSet（如果让你输出没有不怎么走的话）就可以了。 周五电面，拜帖。

flashpacker 发表于 2016-2-11 09:02
我觉得直接DFS就可以了吧，不需要额外空间，每次用过的matrix位置改为一个其余字符

就是用完再改回来就行了， 这个最intuitive了。

leetcode上有,word search,用DFS做的,
BFS怎么做啊

BFS会超时...
If you use BFS, you have to record the positions visited for each path, which can get Time Limit Exceeded.

private static class Cell{
        int x;
        int y;
        Set<List<Integer>> path;
        private Cell(int x, int y) {
            this.x = x;
            this.y = y;
            this.path = new LinkedHashSet<>();
        }
    }
    public boolean findWord(char[][] matrix, String target) {
        if (matrix == null || matrix.length == 0
                || matrix[0].length == 0 || target == null || target.length() == 0) {
            return false;
        }

        int[][] dirs = new int[][] {{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1, -1},{1, -1},{-1, 1}};
        int row = matrix.length;
        int col = matrix[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == target.charAt(0)) {
                    if (helper(matrix, i, j, dirs, target)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    public boolean helper(char[][] matrix, int x, int y, int[][] dirs, String target) {
        int row = matrix.length;
        int col = matrix[0].length;
        int step = 0;
        Queue<Cell> queue = new LinkedList<>();
        Cell first = new Cell(x, y);
        first.path.add(Arrays.asList(x, y));
        queue.add(first); // 没加进去
        while (!queue.isEmpty()) {
            Cell currCell = queue.poll();
            step++;
            if (step == target.length()) {
                return true;
            }
            for (int[] dir : dirs) {
                int nextX = currCell.x + dir[0];
                int nextY = currCell.y + dir[1];
                List<Integer> nextPos = Arrays.asList(nextX, nextY);
                if (nextX >= 0 && nextX < row
                        && nextY >= 0 && nextY < col
                        && !currCell.path.contains(nextPos)
                        && matrix[nextX][nextY] == target.charAt(step)) {
                    Cell newCell = new Cell(nextX, nextY);
                    newCell.path = new LinkedHashSet<>(currCell.path);
                    newCell.path.add(nextPos);
                    queue.offer(newCell);
                }
            }
        }
        return false;
    }

想问下楼主有消息了么？