Find Word Path in Grid
/*
After catching your classroom students cheating before, you realize your students are getting craftier and hiding words in 2D grids of letters. The word may start anywhere in the grid, and consecutive letters can be either immediately below or immediately to the right of the previous letter.
Given a grid and a word, write a function that returns the location of the word in the grid as a list of coordinates. If there are multiple matches, return any one.
grid1 = [
['c', 'c', 'x', 't', 'i', 'b'],
['c', 'c', 'a', 't', 'n', 'i'],
['a', 'c', 'n', 'n', 't', 't'],
['t', 'c', 's', 'i', 'p', 't'],
['a', 'o', 'o', 'o', 'a', 'a'],
['o', 'a', 'a', 'a', 'o', 'o'],
['k', 'a', 'i', 'c', 'k', 'i'],
]
word1 = "catnip"
word2 = "cccc"
word3 = "s"
word4 = "bit"
word5 = "aoi"
word6 = "ki"
word7 = "aaa"
word8 = "ooo"
grid2 = [['a']]
word9 = "a"
find_word_location(grid1, word1) => [ (1, 1), (1, 2), (1, 3), (2, 3), (3, 3), (3, 4) ]
find_word_location(grid1, word2) =>
[(0, 1), (1, 1), (2, 1), (3, 1)]
OR [(0, 0), (1, 0), (1, 1), (2, 1)]
OR [(0, 0), (0, 1), (1, 1), (2, 1)]
OR [(1, 0), (1, 1), (2, 1), (3, 1)]
find_word_location(grid1, word3) => [(3, 2)]
find_word_location(grid1, word4) => [(0, 5), (1, 5), (2, 5)]
find_word_location(grid1, word5) => [(4, 5), (5, 5), (6, 5)]
find_word_location(grid1, word6) => [(6, 4), (6, 5)]
find_word_location(grid1, word7) => [(5, 1), (5, 2), (5, 3)]
find_word_location(grid1, word8) => [(4, 1), (4, 2), (4, 3)]
find_word_location(grid2, word9) => [(0, 0)]
Complexity analysis variables:
r = number of rows
c = number of columns
w = length of the word
*/Similar as https://leetcode.com/problems/word-search-ii/ https://stackoverflow.com/questions/63573254/finding-locations-of-words-as-lists-of-coordinates-in-a-grid-of-letters
这个题目只能向两个方向。right and down走
import java.util.*;
public class FindPathInGrid {
public static void main(String[] args)
{
char[][] grid = {
{'c', 'c', 'x', 't', 'i', 'b'},
{'c', 'c', 'a', 't', 'n', 'i'},
{'a', 'c', 'n', 'n', 't', 't'},
{'t', 'c', 's', 'i', 'p', 't'},
{'a', 'o', 'o', 'o', 'a', 'a'},
{'o', 'a', 'a', 'a', 'o', 'o'},
{'k', 'a', 'i', 'c', 'k', 'i'},
};
String word1 = "catnip";
// Sample output:[ (1, 1), (1, 2), (1, 3), (2, 3), (3, 3), (3, 4) ]
List<int[]> path1 = findPath(grid, word1);
for(int[] element: path1)
{
System.out.println("Path 1 has:");
System.out.println("[" + element[0] + ", " + element[1] + "]");
}
String word2 = "cccc";
// [(0, 1), (1, 1), (2, 1), (3, 1)] OR [(0, 0), (1, 0), (1, 1), (2, 1)] OR
// [(0, 0), (0, 1), (1, 1), (2, 1)] OR [(1, 0), (1, 1), (2, 1), (3, 1)]
List<int[]> path2 = findPath(grid, word2);
for(int[] element: path2)
{
System.out.println("Path 2 has:");
System.out.println("[" + element[0] + ", " + element[1] + "]");
}
String word3 = "s";
// [(3, 2)]
List<int[]> path3 = findPath(grid, word3);
for(int[] element: path3)
{
System.out.println("Path 3 has:");
System.out.println("[" + element[0] + ", " + element[1] + "]");
}
String word4 = "bit";
//[(0, 5), (1, 5), (2, 5)]
List<int[]> path4 = findPath(grid, word4);
for(int[] element: path4)
{
System.out.println("Path 4 has:");
System.out.println("[" + element[0] + ", " + element[1] + "]");
}
String word5 = "aoi";
//[(4, 5), (5, 5), (6, 5)]
List<int[]> path5 = findPath(grid, word5);
for(int[] element: path5)
{
System.out.println("Path 5 has:");
System.out.println("[" + element[0] + ", " + element[1] + "]");
}
}
public static List<int[]> findPath(char[][] board, String word)
{
boolean[][] visited = new boolean[board.length][board[0].length];
Map<String, Boolean> prefixMap = buildMap(word);
List<int[]> path = new ArrayList<>();
List<List<int[]>> allPossiblePaths = new ArrayList<>();
for(int i = 0; i< board.length; i++)
{
for(int j = 0; j< board[0].length; j++)
{
if(board[i][j] == word.charAt(0))
{
dfs(board, i, j, String.valueOf(board[i][j]), prefixMap, visited, path, allPossiblePaths);
}
}
}
return allPossiblePaths.get(0);
}
public static void dfs(char[][] board,
int x,
int y,
String current,
Map<String, Boolean> prefixMap,
boolean[][] visited,
List<int[]> path,
List<List<int[]>> allPossiblePaths)
{
if(!prefixMap.containsKey(current))
{
return;
}
path.add(new int[]{x,y});
visited[x][y] = true;
if(prefixMap.get(current))
{
allPossiblePaths.add(new ArrayList<>(path));
path.remove(path.size()-1);
return;
}
int[] directX = new int[]{1,0};
int[] directY = new int[]{0,1};
for(int i = 0; i< 2; i++)
{
int nextX = x + directX[i];
int nextY = y + directY[i];
if(isBound(board, nextX, nextY) && !visited[nextX][nextY])
{
dfs(board, nextX, nextY, current+board[nextX][nextY], prefixMap, visited, path, allPossiblePaths);
}
}
visited[x][y] = false;
path.remove(path.size()-1);
}
public static Map<String, Boolean> buildMap(String word)
{
Map<String, Boolean> res = new HashMap<>();
for(int i = 0; i< word.length()-1; i++)
{
String current = word.substring(0, i+1);
if(!res.containsKey(current))
{
res.put(current, false);
}
}
res.put(word, true);
return res;
}
public static boolean isBound(char[][] matrix, int i, int j)
{
return i>=0 && i<matrix.length && j>=0 && j<matrix[0].length;
}
}
Last updated