BFS

Leetcode 127

class Solution {
private boolean judge(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        int count = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                count++;
            }
        }
        return count == 1;
    }

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int size = wordList.size();
        Queue<String> queue = new LinkedList<>();
        boolean[] visited = new boolean[size];
        for (int i = 0; i < size; i++) {
            String temp = wordList.get(i);
            if (judge(beginWord, temp) == true) {
                visited[i] = true;
                queue.offer(temp);
            }
        }
        int level = 1;
        while (!queue.isEmpty()) {
            int thisLevelSize = queue.size();
            level++;
            for (int i = 0; i < thisLevelSize; i++) {
                String temp = queue.poll();
                if (temp.equals(endWord)) {
                    return level;
                }
                for (int j = 0; j < size; j++) {
                    if (visited[j] == false && judge(temp, wordList.get(j))) {
                        visited[j] = true;
                        queue.offer(wordList.get(j));
                    }
                }
            }
        }
        return 0;
    }
}

Leetcode1293

class Node {
    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public int getVal() {
        return val;
    }

    public void setX(int x) {
        this.x = x;
    }

    public void setY(int y) {
        this.y = y;
    }

    public void setVal(int val) {
        this.val = val;
    }

    int x;
    int y;
    int val;

    public Node(int x, int y, int val) {
        this.x = x;
        this.y = y;
        this.val = val;
    }
}
class Solution {
    final static int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    
    public int shortestPath(int[][] grid, int k) {
        int row = grid.length;
        int col = grid[0].length;
        if (row == 1 && col == 1) {
            return 0;
        }
        int min = Math.min(k, row + col - 3);
        boolean[][][] visited = new boolean[row][col][k + 1];
        Queue<Node> que = new LinkedList<>();
        que.offer(new Node(0, 0, k));
        visited[0][0][k] = true;
        for (int step = 1; que.size() > 0; step++) {
            int size = que.size();
            for (int j = 0; j < size; j++) {
                Node tempNode = que.poll();
                for (int m = 0; m < DIRS.length; m++) {
                    int tempX = tempNode.getX() + DIRS[m][0];
                    int tempY = tempNode.getY() + DIRS[m][1];
                    int val = tempNode.getVal();
                    if (tempX < 0 || tempX >= row || tempY < 0 || tempY >= col) {
                        continue;
                    }
                    if (tempX == (row - 1) && tempY == (col - 1)) {
                        return step;
                    }
                    if (grid[tempX][tempY] == 0 && visited[tempX][tempY][val] == false) {
                        que.offer(new Node(tempX, tempY, val));
                        visited[tempX][tempY][val] = true;
                    } else if (grid[tempX][tempY] == 1 && val > 0 && visited[tempX][tempY][val - 1] == false){
                        que.offer(new Node(tempX, tempY, val - 1));
                        visited[tempX][tempY][val - 1] = true;
                    }
                }
            }
        }
        return -1;
    }
}

DFS

leetcode 332

class Solution {
    boolean dfs(Map<String, List<String>> map, List<String> result, int length) {
        if (result.size() == length) {
            return true;
        }
        System.out.println();
        List<String> list = map.get(result.get(result.size() - 1));
        if (list == null) {
            return false;
        }
        for (int i = 0; i < list.size(); i++) {
            result.add(list.get(i));
            list.remove(i);
            if (dfs(map, result, length) == true) {
                return true;
            }
            list.add(i, result.get(result.size() - 1));
            result.remove(result.size() - 1);
        }
        return false;
    }
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < tickets.size(); i++) {
            List<String> list = tickets.get(i);
            String from = list.get(0);
            String to = list.get(1);
            List<String> temp = map.get(from);
            if (temp == null) {
                temp = new ArrayList<>();
                map.put(from, temp);
            }
            temp.add(to);
        }
        for (Map.Entry<String, List<String>> entry : map.entrySet()) {
            Collections.sort(entry.getValue());
        }
        List<String> result = new LinkedList<>();
        result.add("JFK");
        dfs(map, result, tickets.size() + 1);
        return  result;
    }
}

leetcode