LC127. Word Ladder
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
class Solution {
//大致的过程就是
// hit --> hot --> dot, lot --> (dog, lot), log -->cog(和最末单词比较是一致的返回5)
public int ladderLength(String beginWord, String endWord, List<String> wordList)
{
Set<String> dict = new HashSet<>();
for (String word : wordList){
dict.add(word);
} // 把单词放进去dict里
HashSet<String> set = new HashSet<>();//用来放所有演变的单词
Queue<String> q = new LinkedList<String>();
q.offer(beginWord);
set.add(beginWord);
int len = 1;
while(!q.isEmpty()){
len++;
int size = q.size();
for (int i = 0; i < size; i++){
String word = q.poll();
for(String nextWord : getNextWord(word, dict)){
if(set.contains(nextWord)) continue;//如果set已经含有了这个单词跳过
if(nextWord.equals(endWord)) return len;//如果和目标单词一样说明找到了，返回长度
set.add(nextWord); //都是不的话把单词放进set里
q.offer(nextWord);//队列里也加入这个单词
}
}
}
return 0;
}
private ArrayList<String> getNextWord(String word, Set<String> dict){
ArrayList<String> nextWords = new ArrayList<>();
for (char c = 'a'; c <= 'z'; c++){
for (int i = 0; i < word.length(); i++){
if (c == word.charAt(i)) continue;// find first element
String nextWord = replace(word, i, c);
if (dict.contains(nextWord)){
nextWords.add(nextWord);
}
}
}
return nextWords;
}
private String replace(String s, int index, char c){
char[] chars = s.toCharArray();
chars[index] = c;
return new String(chars);
}
}
LC130. Surrounded Regions
class Solution {
public void solve(char[][] board) {
int n = board.length;
if(n == 0) return;
int m = board[0].length;
for (int i = 0; i < n; i++){
bfs(board, i, 0);
bfs(board, i, m-1);
}
for (int j = 0; j < m; j++){
bfs(board, 0, j);
bfs(board, n-1, j);
}
for (int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if (board[i][j] == 'W'){
board[i][j] = 'O';
} else {
board[i][j] = 'X';
}
}
}
}
//这个函数的意思是只要检查出边界是0，再看有多少和边界联通的0，只要有联通的就不能改为x
private void bfs(char[][] board, int sx, int sy){
if (board[sx][sy] == 'X') return;
int n = board.length;
int m = board[0].length;
int[] dx = {0,1,0,-1};
int[] dy = {1,0,-1,0};
Queue<Integer> qx = new LinkedList<>();
Queue<Integer> qy = new LinkedList<>();
qx.offer(sx);
qy.offer(sy);
board[sx][sy] = 'W'; //initialize board element to W
while(!qx.isEmpty()){
int cx = qx.poll();
int cy = qy.poll();
for(int i = 0; i < 4; i++){
int nx = cx + dx[i];
int ny = cy + dy[i];//find 0-right, 1-down, 2-left, 3-top element of a element
if(nx >= 0 && nx < n && ny >=0 && ny < m && board[nx][ny] == 'O'){
board[nx][ny] = 'W';
qx.offer(nx);
qy.offer(ny);
}
}
}
}
}
LC200. Number of Islands
Input:
11110
11010
11000
00000
Output: 1
public int numIslands(char[][] grid) {
if(grid == null || grid.length == 0 || grid[0].length == 0) return 0;
int m = grid.length; //设置图长
int n = grid[0].length;//设置图宽
int islands = 0;//设置岛的大小
for (int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if (grid[i][j] == '1'){//如果遇到1就开始计算所有联通的区域
bfs(grid, i, j);
islands++;//计算完成岛的数量加1
}
}
}
return islands;
}
private void bfs(char[][] grid, int x, int y){
int[] dx = {0, 1, 0, -1};//x方向变量
int[] dy = {1, 0, -1, 0};//y方向变量
int m = grid.length;
int n = grid[0].length;
Queue<Integer> qx = new LinkedList<>();
Queue<Integer> qy = new LinkedList<>();//xy坐标分别加上队列
qx.offer(x);
qy.offer(y);
grid[x][y] = '0';
while(!qx.isEmpty()){
int cx = qx.poll();
int cy = qy.poll(); //cx是从队列里取出的元素
for (int i = 0; i < 4; i++){
int nx = cx + dx[i];
int ny = cy + dy[i];//nx是计算输入点的上下左右四个点
if (!(nx >= 0 && nx < m && ny >=0 && ny < n)) continue;
if (grid[nx][ny] == '1'){
grid[nx][ny] = '0';//已经扫过的元素要变零防止再扫一遍
qx.offer(nx);
qy.offer(ny); //把新的xy坐标放进队列里继续搜索相邻的，凡是搜索到的都标为0，这个函数是搜索所有可能的联通点
}
}
}
