Reference: Link

If a problem is about graph or tree, we should consider bfs, dfs, backtracking as the solution. When we are using bfs, we need to use queue to store nodes that we have traversed. And we need to mark traversed nodes so that we will not traverse this node again. The test point of some questions is to use bfs to solve the shortest path problem.

1091. Shortest Path in Binary Matrix(Medium)

This problem is a graph problem. The difference between this problem and common problems is adjacent cells are connected 8-directionally. And we need to get the shortest path in this problem. Therefore, we need to empty our queue in each iteration so that the length of path will not be larger. This means we need to get all possible adjacent cells in each step and check if these cells contain end position. We need a queue to traverse all possible cells. If we visit a cell, we change it value to 1 so that we will not visit it again.

public int shortestPathBinaryMatrix(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    int[][] direction = {{1, -1}, {1, 0}, {1, 1}, {0, -1}, {0, 1}, {-1, -1}, {-1, 0}, {-1, 1}};
    int ans = 0;
    
    if(grid[0][0]==1||grid[m-1][n-1]==1||m==0||n==0)return -1;
    
    Queue<int[]>queue = new LinkedList<int[]>();
    queue.add(new int[]{0,0});
    
    
    while(!queue.isEmpty()){
        ans++;
        int size = queue.size();
        while(size>0){
            size--;
            int[]start = queue.poll();
            int x = start[0];
            int y = start[1];
            
            if(grid[x][y]==1)continue;
            
            if(x==grid.length-1 && y==grid[0].length-1){
                return ans;
            }
            
            grid[x][y]=1;
            
            for(int[] dict:direction){
                int newx = x + dict[0];
                int newy = y + dict[1];
                int []newpos = new int[]{newx,newy};
                if(valid(newpos,grid))
                    queue.add(newpos);
            }
        }
    }
    return -1;
}

public boolean valid(int[]next,int[][]grid){
    
    if(next[0]>=0&&next[1]>=0&&next[0]<grid.length&&next[1]<grid[0].length)
        return true;
    else
        return false;
}

127. Word Ladder (Medium)

The idea of this problem is to find the shortest path in a graph. This graph is consist of strings in ‘wordList’. Each node is a string. And we need to find the shortest path from ‘beginWord’ to ‘endWord’. So we need to use bfs to solve this problem. We use a hashmap to record the length of the path. And this hashmap can also tell us if a node is already visited. The key is the string in ‘wordList’. The value is the length of the path from ‘startWord’ to the key. We store all strings in a hash set but not list, because it can improve the efficiency to find the target string. In each iteration, we get a string from the queue. And change one character of this string to find if new string is in the hash set. If it’s in the hashset and it’s not in the hashmap, we can add it to the queue and map. If it’s the endword, we can return the answer.

Time complexity is O(mn). m is the size of ‘wordList’. n is the average length of the string. Space complexity is O(m+n). Here is the link. public int ladderLength(String beginWord, String endWord, List wordList) { Queuequeue = new LinkedList(); queue.add(beginWord);

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Queue<String>queue = new LinkedList<String>();
    queue.add(beginWord);
    
    HashMap<String,Integer>map = new HashMap();
    map.put(beginWord,1);
    HashSet<String>wordset = new HashSet();
    
    for(String str:wordList)wordset.add(str);

    while(!queue.isEmpty()){

        String word = queue.poll();
            
        for(int i =0;i<word.length();i++){
            for(Character letter = 'a';letter<='z';letter++){
                String newword = word.substring(0,i)+String.valueOf(letter)+word.substring(i+1);
                if(wordset.contains(newword)){
                    if(newword.equals(endWord) )return map.get(word)+1;
                    if(!map.containsKey(newword)){
                        queue.add(newword);
                        map.put(newword,map.get(word)+1);
                    }
                }
            }
        }
    }

    return 0;
}