Homework Help is Here – Start Your Trial Now!
Engineering
Data Structures and Algorithms
You are given an m x n board and a word. You need to check if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are horizontally or vertically neighboring. The same letter cell may not be used more than once. Select the optimal solution in terms of time complexity. If time complexities are same for multiple solutions, select the one with optimal space complexity. function exist(board, word):    for i from 0 to number of rows in board:        for j from 0 to number of columns in board:            if dfs(board, word, i, j, 0):                return true    return falsefunction dfs(board, word, i, j, index):    if index == length of word:        return true    if i < 0 or i >= number of rows in board or j < 0 or j >= number of columns in board or board[i][j] != word[index]:        return false    temp = board[i][j]    board[i][j] = '#'    found = (dfs(board, word, i+1, j, index+1) or             dfs(board, word, i-1, j, index+1) or             dfs(board, word, i, j+1, index+1) or             dfs(board, word, i, j-1, index+1))    board[i][j] = temp    return found function exist(board, word):    for i from 0 to number of rows in board:        for j from 0 to number of columns in board:            if bfs(board, word, i, j):                return true    return falsefunction bfs(board, word, i, j):    queue = [(i, j, 0)]    while queue:        x, y, index = queue.pop(0)        if index == length of word:            return true        if x < 0 or x >= number of rows in board or y < 0 or y >= number of columns in board or board[x][y] != word[index]:            continue        temp = board[x][y]        board[x][y] = '#'        queue.append((x+1, y, index+1))        queue.append((x-1, y, index+1))        queue.append((x, y+1, index+1))        queue.append((x, y-1, index+1))        board[x][y] = temp    return false function exist(board, word):    for i from 0 to number of rows in board:        for j from 0 to number of columns in board:            if dfs(board, word, i, j, 0):                return true    return falsefunction dfs(board, word, i, j, index):    if index == length of word:        return true    if i < 0 or i >= number of rows in board or j < 0 or j >= number of columns in board or board[i][j] != word[index]:        return false    found = (dfs(board, word, i+1, j, index+1) or             dfs(board, word, i-1, j, index+1) or             dfs(board, word, i, j+1, index+1) or             dfs(board, word, i, j-1, index+1))    return found

You are given an m x n board and a word. You need to check if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are horizontally or vertically neighboring. The same letter cell may not be used more than once. Select the optimal solution in terms of time complexity. If time complexities are same for multiple solutions, select the one with optimal space complexity. function exist(board, word):    for i from 0 to number of rows in board:        for j from 0 to number of columns in board:            if dfs(board, word, i, j, 0):                return true    return falsefunction dfs(board, word, i, j, index):    if index == length of word:        return true    if i < 0 or i >= number of rows in board or j < 0 or j >= number of columns in board or board[i][j] != word[index]:        return false    temp = board[i][j]    board[i][j] = '#'    found = (dfs(board, word, i+1, j, index+1) or             dfs(board, word, i-1, j, index+1) or             dfs(board, word, i, j+1, index+1) or             dfs(board, word, i, j-1, index+1))    board[i][j] = temp    return found function exist(board, word):    for i from 0 to number of rows in board:        for j from 0 to number of columns in board:            if bfs(board, word, i, j):                return true    return falsefunction bfs(board, word, i, j):    queue = [(i, j, 0)]    while queue:        x, y, index = queue.pop(0)        if index == length of word:            return true        if x < 0 or x >= number of rows in board or y < 0 or y >= number of columns in board or board[x][y] != word[index]:            continue        temp = board[x][y]        board[x][y] = '#'        queue.append((x+1, y, index+1))        queue.append((x-1, y, index+1))        queue.append((x, y+1, index+1))        queue.append((x, y-1, index+1))        board[x][y] = temp    return false function exist(board, word):    for i from 0 to number of rows in board:        for j from 0 to number of columns in board:            if dfs(board, word, i, j, 0):                return true    return falsefunction dfs(board, word, i, j, index):    if index == length of word:        return true    if i < 0 or i >= number of rows in board or j < 0 or j >= number of columns in board or board[i][j] != word[index]:        return false    found = (dfs(board, word, i+1, j, index+1) or             dfs(board, word, i-1, j, index+1) or             dfs(board, word, i, j+1, index+1) or             dfs(board, word, i, j-1, index+1))    return found

icon
Related questions
Question

You are given an m x n board and a word. You need to check if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are horizontally or vertically neighboring. The same letter cell may not be used more than once. Select the optimal solution in terms of time complexity. If time complexities are same for multiple solutions, select the one with optimal space complexity.

function exist(board, word):
    for i from 0 to number of rows in board:
        for j from 0 to number of columns in board:
            if dfs(board, word, i, j, 0):
                return true
    return false

function dfs(board, word, i, j, index):
    if index == length of word:
        return true
    if i < 0 or i >= number of rows in board or j < 0 or j >= number of columns in board or board[i][j] != word[index]:
        return false
    temp = board[i][j]
    board[i][j] = '#'
    found = (dfs(board, word, i+1, j, index+1) or
             dfs(board, word, i-1, j, index+1) or
             dfs(board, word, i, j+1, index+1) or
             dfs(board, word, i, j-1, index+1))
    board[i][j] = temp
    return found
function exist(board, word):
    for i from 0 to number of rows in board:
        for j from 0 to number of columns in board:
            if bfs(board, word, i, j):
                return true
    return false

function bfs(board, word, i, j):
    queue = [(i, j, 0)]
    while queue:
        x, y, index = queue.pop(0)
        if index == length of word:
            return true
        if x < 0 or x >= number of rows in board or y < 0 or y >= number of columns in board or board[x][y] != word[index]:
            continue
        temp = board[x][y]
        board[x][y] = '#'
        queue.append((x+1, y, index+1))
        queue.append((x-1, y, index+1))
        queue.append((x, y+1, index+1))
        queue.append((x, y-1, index+1))
        board[x][y] = temp
    return false
function exist(board, word):
    for i from 0 to number of rows in board:
        for j from 0 to number of columns in board:
            if dfs(board, word, i, j, 0):
                return true
    return false

function dfs(board, word, i, j, index):
    if index == length of word:
        return true
    if i < 0 or i >= number of rows in board or j < 0 or j >= number of columns in board or board[i][j] != word[index]:
        return false
    found = (dfs(board, word, i+1, j, index+1) or
             dfs(board, word, i-1, j, index+1) or
             dfs(board, word, i, j+1, index+1) or
             dfs(board, word, i, j-1, index+1))
    return found
AI-Generated Solution
AI-generated content may present inaccurate or offensive content that does not represent bartleby’s views.
steps

Unlock instant AI solutions

Tap the button
to generate a solution

SEE SOLUTION