Dado un tablero de array de caracteres y una string Word , la tarea es verificar si Word existe en el tablero construido a partir de una secuencia de caracteres adyacentes horizontal y verticalmente solamente. Cada carácter se puede utilizar sólo una vez.
Ejemplos:
Entrada:
tablero = { {‘A’, ‘B’, ‘C’, ‘E’}, {‘S’, ‘F’, ‘C’, ‘S’}, {‘A’, ‘D’, ‘E’, ‘E’} }
Palabra = “VER”
Salida: Verdadero
Explicación: “VER” se puede formar usando caracteres en (1, 3)[S], (2, 3)[E] y (2, 2 )[MI].Entrada:
tablero = { {‘A’, ‘B’, ‘C’, ‘E’}, {‘S’, ‘F’, ‘C’, ‘S’}, {‘A’, ‘D’, ‘E’, ‘E’} }
Palabra = “ABCB”
Salida: Falso
Explicación: “ABCB” no se puede formar usando caracteres adyacentes sin repetición.
Enfoque: El enfoque para resolver este problema es recorrer todos los caracteres de la array y encontrar la aparición del primer carácter de la palabra. Siempre que lo encuentre, siga revisando recursivamente sus celdas horizontales y verticales adyacentes para el siguiente carácter. Repite este proceso hasta encontrar todos los personajes uno por uno. Cualquier instancia en la que todos los caracteres coincidan significa que se encuentra Word . Si no se produce tal instancia, no se encuentra Word .
A continuación se muestra la implementación de la lógica anterior:
C++
// C++ Program to check if a given
// word can be formed from the
// adjacent characters in a matrix
// of characters
#include <bits/stdc++.h>
using namespace std;
// Function to check if the word exists
bool checkWord(vector<vector<char> >& board,
string& word, int index,
int row, int col)
{
// If index exceeds board range
if (row < 0 || col < 0
|| row >= board.size()
|| col >= board[0].size())
return false;
// If the current cell does not
// contain the required character
if (board[row][col] != word[index])
return false;
// If the cell contains the required
// character and is the last character
// of the word required to be matched
else if (index == word.size() - 1)
// Return true as word is found
return true;
char temp = board[row][col];
// Mark cell visited
board[row][col] = '*';
// Check Adjacent cells
// for the next character
if (checkWord(board, word,
index + 1, row + 1, col)
|| checkWord(board, word,
index + 1, row - 1, col)
|| checkWord(board, word,
index + 1, row, col + 1)
|| checkWord(board, word,
index + 1, row, col - 1)) {
board[row][col] = temp;
return true;
}
// Restore cell value
board[row][col] = temp;
return false;
}
// Driver Code
int main()
{
vector<vector<char> > board
= { { 'A', 'B', 'C', 'E' },
{ 'S', 'F', 'C', 'S' },
{ 'A', 'D', 'E', 'E' } };
string word = "CFDASABCESEE";
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[0].size(); j++) {
if (board[i][j] == word[0]
&& checkWord(
board, word,
0, i, j)) {
cout << "True" << '\n';
return 0;
}
}
}
cout << "False" << '\n';
return 0;
}
Java
// Java Program to check if a given
// word can be formed from the
// adjacent characters in a matrix
// of characters
import java.util.*;
class GFG{
// Function to check if the word exists
static boolean checkWord(char [][]board,
String word, int index,
int row, int col)
{
// If index exceeds board range
if (row < 0 || col < 0 ||
row >= board.length ||
col >= board[0].length)
return false;
// If the current cell does not
// contain the required character
if (board[row][col] != word.charAt(index))
return false;
// If the cell contains the required
// character and is the last character
// of the word required to be matched
else if (index == word.length() - 1)
// Return true as word is found
return true;
char temp = board[row][col];
// Mark cell visited
board[row][col] = '*';
// Check Adjacent cells
// for the next character
if (checkWord(board, word,
index + 1, row + 1, col) ||
checkWord(board, word,
index + 1, row - 1, col) ||
checkWord(board, word,
index + 1, row, col + 1) ||
checkWord(board, word,
index + 1, row, col - 1))
{
board[row][col] = temp;
return true;
}
// Restore cell value
board[row][col] = temp;
return false;
}
// Driver Code
public static void main(String[] args)
{
char[][] board = { { 'A', 'B', 'C', 'E' },
{ 'S', 'F', 'C', 'S' },
{ 'A', 'D', 'E', 'E' } };
String word = "CFDASABCESEE";
for (int i = 0; i < board.length; i++)
{
for (int j = 0; j < board[0].length; j++)
{
if (board[i][j] == word.charAt(0) &&
checkWord(board, word, 0, i, j))
{
System.out.println("True");
return;
}
}
}
System.out.println("False");
}
}
// This code is contributed by Rajput-Ji
Python3
# Python 3 Program to check if a given
# word can be formed from the
# adjacent characters in a matrix
# of characters
# Function to check if
# the word exists
def checkWord(board, word,
index, row, col):
# If index exceeds board range
if (row < 0 or col < 0 or
row >= len(board) or
col >= len(board[0])):
return False
# If the current cell does not
# contain the required character
if (board[row][col] != word[index]):
return False
# If the cell contains the required
#character and is the last character
# of the word required to be matched
elif (index == len(word) - 1):
# Return true as word is found
return True
temp = board[row][col]
# Mark cell visited
board[row][col] = '*'
# Check Adjacent cells
# for the next character
if (checkWord(board, word,
index + 1,
row + 1, col) or
checkWord(board, word,
index + 1,
row - 1, col) or
checkWord(board, word,
index + 1,
row, col + 1) or
checkWord(board, word,
index + 1,
row, col - 1)):
board[row][col] = temp
return True
# Restore cell value
board[row][col] = temp
return False
# Driver Code
if __name__ == "__main__":
board = [['A', 'B', 'C', 'E'],
['S', 'F', 'C', 'S'],
['A', 'D', 'E', 'E']]
word = "CFDASABCESEE"
f = 0
for i in range (len(board)):
for j in range (len(board[0])):
if (board[i][j] == word[0] and
checkWord(board, word,
0, i, j)):
print ("True" )
f = 1
break
if f == 1:
break
if f == 0:
print ("False")
# This code is contributed by Chitranayal
C#
// C# program to check if a given word
// can be formed from the adjacent
// characters in a matrix of characters
using System;
class GFG{
// Function to check if the word exists
static bool checkWord(char [,]board, String word,
int index, int row, int col)
{
// If index exceeds board range
if (row < 0 || col < 0 ||
row >= board.GetLength(0) ||
col >= board.GetLength(1))
return false;
// If the current cell does not
// contain the required character
if (board[row, col] != word[index])
return false;
// If the cell contains the required
// character and is the last character
// of the word required to be matched
else if (index == word.Length - 1)
// Return true as word is found
return true;
char temp = board[row, col];
// Mark cell visited
board[row, col] = '*';
// Check adjacent cells
// for the next character
if (checkWord(board, word,
index + 1, row + 1, col) ||
checkWord(board, word,
index + 1, row - 1, col) ||
checkWord(board, word,
index + 1, row, col + 1) ||
checkWord(board, word,
index + 1, row, col - 1))
{
board[row, col] = temp;
return true;
}
// Restore cell value
board[row, col] = temp;
return false;
}
// Driver Code
public static void Main(String[] args)
{
char[,] board = { { 'A', 'B', 'C', 'E' },
{ 'S', 'F', 'C', 'S' },
{ 'A', 'D', 'E', 'E' } };
String word = "CFDASABCESEE";
for(int i = 0; i < board.GetLength(0); i++)
{
for(int j = 0; j < board.GetLength(1); j++)
{
if (board[i, j] == word[0] &&
checkWord(board, word, 0, i, j))
{
Console.WriteLine("True");
return;
}
}
}
Console.WriteLine("False");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to check if a given word
// can be formed from the adjacent
// characters in a matrix of characters
// Function to check if the word exists
function checkWord(board, word, index, row, col)
{
// If index exceeds board range
if (row < 0 || col < 0 ||
row >= board.length ||
col >= board[0].length)
return false;
// If the current cell does not
// contain the required character
if (board[row][col] !== word[index])
return false;
// If the cell contains the required
// character and is the last character
// of the word required to be matched
else if (index === word.length - 1)
// Return true as word is found
return true;
var temp = board[row][col];
// Mark cell visited
board[row][col] = "*";
// Check adjacent cells
// for the next character
if (checkWord(board, word,
index + 1, row + 1, col) ||
checkWord(board, word,
index + 1, row - 1, col) ||
checkWord(board, word,
index + 1, row, col + 1) ||
checkWord(board, word,
index + 1, row, col - 1))
{
board[row][col] = temp;
return true;
}
// Restore cell value
board[row][col] = temp;
return false;
}
// Driver Code
var board = [ [ "A", "B", "C", "E" ],
[ "S", "F", "C", "S" ],
[ "A", "D", "E", "E" ],];
var word = "CFDASABCESEE";
var f = 0;
for(var i = 0; i < board.length; i++)
{
for(var j = 0; j < board[0].length; j++)
{
if (board[i][j] === word[0] &&
checkWord(board, word, 0, i, j))
{
document.write("True");
f = 1;
}
}
if (f === 1)
{
i = board.length + 1;
}
}
if (f === 0)
{
document.write("False");
}
// This code is contributed by rdtank
</script>
Producción:
True
Publicación traducida automáticamente
Artículo escrito por AnshulVerma1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA