Dada una array de caracteres de 2 dimensiones y una string, necesitamos encontrar la string dada en una array de caracteres de 2 dimensiones, de modo que los caracteres individuales puedan estar presentes de izquierda a derecha, de derecha a izquierda, de arriba hacia abajo o de abajo hacia arriba.
Ejemplos:
Input : a ={
{D,D,D,G,D,D},
{B,B,D,E,B,S},
{B,S,K,E,B,K},
{D,D,D,D,D,E},
{D,D,D,D,D,E},
{D,D,D,D,D,G}
}
str= "GEEKS"
Output :2
Input : a = {
{B,B,M,B,B,B},
{C,B,A,B,B,B},
{I,B,G,B,B,B},
{G,B,I,B,B,B},
{A,B,C,B,B,B},
{M,C,I,G,A,M}
}
str= "MAGIC"
Output :3
Hemos discutido un problema más simple para encontrar si una palabra existe o no en una array .
Acercarse:
1. Para contar todas las ocurrencias, seguimos un enfoque simple de fuerza bruta.
2. Recorrer cada carácter de la array y tomar cada carácter como inicio de la string a encontrar.
3. Intenta buscar en todas las direcciones posibles.
4. Cada vez que encuentre una palabra, aumente el conteo.
5. Después de atravesar la array, cualquiera que sea el valor de la cuenta, será el número de veces que existe una string en la array de caracteres.
Algoritmo:
Paso 1 : recorrer la array carácter por carácter y tomar un carácter como inicio de string
Paso 2 : para cada carácter, busque la string en las cuatro direcciones recursivamente
Paso 3 : si se encuentra una string, aumentamos el conteo
Paso 4 : cuando estamos hecho con un caracter como inicio, repetimos el mismo proceso para el siguiente caracter
Paso 5 – Calcular la suma de conteo para cada caracter
Paso 6 – El conteo final será la respuesta
C++14
// C++ code for finding count
// of string in a given 2D
// character array.
#include <bits/stdc++.h>
using namespace std;
#define ARRAY_SIZE(a) (sizeof(a) / sizeof(*a))
// utility function to search
// complete string from any
// given index of 2d char array
int internalSearch(string needle, int row,
int col, string hay[],
int row_max, int col_max, int xx)
{
int found = 0;
if (row >= 0 && row <= row_max && col >= 0 &&
col <= col_max && needle[xx] == hay[row][col])
{
char match = needle[xx];
xx += 1;
hay[row][col] = 0;
if (needle[xx] == 0)
{
found = 1;
}
else
{
// through Backtrack searching
// in every directions
found += internalSearch(needle, row,
col + 1, hay,
row_max, col_max,xx);
found += internalSearch(needle, row, col - 1,
hay, row_max, col_max,xx);
found += internalSearch(needle, row + 1, col,
hay, row_max, col_max,xx);
found += internalSearch(needle, row - 1, col,
hay, row_max, col_max,xx);
}
hay[row][col] = match;
}
return found;
}
// Function to search the string in 2d array
int searchString(string needle, int row, int col,
string str[], int row_count,
int col_count)
{
int found = 0;
int r, c;
for (r = 0; r < row_count; ++r)
{
for (c = 0; c < col_count; ++c)
{
found += internalSearch(needle, r, c, str,
row_count - 1,
col_count - 1, 0);
}
}
return found;
}
// Driver code
int main()
{
string needle = "MAGIC";
string input[] = { "BBABBM",
"CBMBBA",
"IBABBG",
"GOZBBI",
"ABBBBC",
"MCIGAM" };
string str[ARRAY_SIZE(input)];
int i;
for (i = 0; i < ARRAY_SIZE(input); ++i)
{
str[i] = input[i];
}
cout << "count: " << searchString(needle, 0, 0, str,
ARRAY_SIZE(str),
str[0].size()) << endl;
return 0;
}
// This code is contributed by SHUBHAMSINGH8410
C
// C code for finding count
// of string in a given 2D
// character array.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define ARRAY_SIZE(a) (sizeof(a) / sizeof(*a))
// utility function to search
// complete string from any
// given index of 2d char array
int internalSearch(char *needle, int row,
int col, char **hay,
int row_max, int col_max)
{
int found = 0;
if (row >= 0 && row <= row_max && col >= 0 &&
col <= col_max && *needle == hay[row][col])
{
char match = *needle++;
hay[row][col] = 0;
if (*needle == 0) {
found = 1;
} else {
// through Backtrack searching
// in every directions
found += internalSearch(needle, row,
col+1, hay,
row_max, col_max);
found += internalSearch(needle, row, col-1,
hay, row_max, col_max);
found += internalSearch(needle, row+1, col,
hay, row_max, col_max);
found += internalSearch(needle, row-1, col,
hay, row_max, col_max);
}
hay[row][col] = match;
}
return found;
}
// Function to search the string in 2d array
int searchString(char *needle, int row, int col,
char **str, int row_count, int col_count)
{
int found = 0;
int r, c;
for (r = 0; r < row_count; ++r) {
for (c = 0; c < col_count; ++c) {
found += internalSearch(needle, r, c, str,
row_count - 1, col_count - 1);
}
}
return found;
}
// Driver code
int main(void){
char needle[] = "MAGIC";
char *input[] = {
"BBABBM",
"CBMBBA",
"IBABBG",
"GOZBBI",
"ABBBBC",
"MCIGAM"
};
char *str[ARRAY_SIZE(input)];
int i;
for (i = 0; i < ARRAY_SIZE(input); ++i) {
str[i] = malloc(strlen(input[i]));
strcpy(str[i], input[i]);
}
printf("count: %d\n", searchString(needle, 0, 0,
str, ARRAY_SIZE(str), strlen(str[0])));
return 0;
}
Java
// Java code for finding count
// of string in a given 2D
// character array.
import java.util.*;
class GFG{
// Utility function to search
// complete string from any
// given index of 2d char array
static int internalSearch(String needle, int row,
int col, String hay[],
int row_max, int col_max,
int xx)
{
int found = 0;
if (row >= 0 && row <= row_max && col >= 0 &&
col <= col_max && xx < needle.length() &&
needle.charAt(xx) == hay[row].charAt(col))
{
char match = needle.charAt(xx);
xx += 1;
hay[row] = hay[row].substring(0, col) + "0" +
hay[row].substring(col + 1);
if (xx == needle.length())
{
found = 1;
}
else
{
// Through Backtrack searching
// in every directions
found += internalSearch(needle, row,
col + 1, hay,
row_max, col_max,xx);
found += internalSearch(needle, row, col - 1,
hay, row_max, col_max,xx);
found += internalSearch(needle, row + 1, col,
hay, row_max, col_max,xx);
found += internalSearch(needle, row - 1, col,
hay, row_max, col_max,xx);
}
hay[row] = hay[row].substring(0, col) +
match + hay[row].substring(col + 1);
}
return found;
}
// Function to search the string in 2d array
static int searchString(String needle, int row, int col,
String str[], int row_count,
int col_count)
{
int found = 0;
int r, c;
for(r = 0; r < row_count; ++r)
{
for(c = 0; c < col_count; ++c)
{
found += internalSearch(needle, r, c, str,
row_count - 1,
col_count - 1, 0);
}
}
return found;
}
// Driver code
public static void main(String args[])
{
String needle = "MAGIC";
String input[] = { "BBABBM", "CBMBBA",
"IBABBG", "GOZBBI",
"ABBBBC", "MCIGAM" };
String str[] = new String[input.length];
int i;
for(i = 0; i < input.length; ++i)
{
str[i] = input[i];
}
System.out.println("count: " +
searchString(needle, 0, 0, str,
str.length,
str[0].length()));
}
}
// This code is contributed by adityapande88
Python3
# Python code for finding count
# of string in a given 2D
# character array.
# utility function to search
# complete string from any
# given index of 2d array
def internalSearch(ii, needle, row, col, hay,
row_max, col_max):
found = 0
if (row >= 0 and row <= row_max and
col >= 0 and col <= col_max and
needle[ii] == hay[row][col]):
match = needle[ii]
ii += 1
hay[row][col] = 0
if (ii == len(needle)):
found = 1
else:
# through Backtrack searching
# in every directions
found += internalSearch(ii, needle, row,
col + 1, hay, row_max, col_max)
found += internalSearch(ii, needle, row,
col - 1, hay, row_max, col_max)
found += internalSearch(ii, needle, row + 1,
col, hay, row_max, col_max)
found += internalSearch(ii, needle, row - 1,
col, hay, row_max, col_max)
hay[row][col] = match
return found
# Function to search the string in 2d array
def searchString(needle, row, col,strr,
row_count, col_count):
found = 0
for r in range(row_count):
for c in range(col_count):
found += internalSearch(0, needle, r, c,
strr, row_count - 1, col_count - 1)
return found
# Driver code
needle = "MAGIC"
inputt = ["BBABBM","CBMBBA","IBABBG",
"GOZBBI","ABBBBC","MCIGAM"]
strr = [0] * len(inputt)
for i in range(len(inputt)):
strr[i] = list(inputt[i])
print("count: ", searchString(needle, 0, 0, strr,
len(strr), len(strr[0])))
# This code is contributed by SHUBHAMSINGH10
C#
// Include namespace system
using System;
public class GFG
{
// Utility function to search
// complete string from any
// given index of 2d char array
public static int internalSearch(String needle, int row,
int col, String[] hay,
int row_max, int col_max, int xx)
{
var found = 0;
if (row >= 0 && row <= row_max && col >= 0 && col <= col_max && xx < needle.Length && needle[xx] == hay[row][col])
{
var match = needle[xx];
xx += 1;
hay[row] = hay[row].Substring(0,col-0) + "0" +
hay[row].Substring(col + 1);
if (xx == needle.Length)
{
found = 1;
}
else
{
// Through Backtrack searching
// in every directions
found += GFG.internalSearch(needle, row,
col + 1, hay,
row_max, col_max, xx);
found += GFG.internalSearch(needle, row, col - 1,
hay, row_max, col_max, xx);
found += GFG.internalSearch(needle, row + 1, col,
hay, row_max, col_max, xx);
found += GFG.internalSearch(needle, row - 1, col,
hay, row_max, col_max, xx);
}
hay[row] = hay[row].Substring(0,col-0) + match.ToString() + hay[row].Substring(col + 1);
}
return found;
}
// Function to search the string in 2d array
public static int searchString(String needle, int row, int col, String[] str, int row_count, int col_count)
{
var found = 0;
int r;
int c;
for (r = 0; r < row_count; ++r)
{
for (c = 0; c < col_count; ++c)
{
found += GFG.internalSearch(needle, r, c, str, row_count - 1, col_count - 1, 0);
}
}
return found;
}
// Driver code
public static void Main(String[] args)
{
var needle = "MAGIC";
String[] input = {"BBABBM", "CBMBBA", "IBABBG", "GOZBBI", "ABBBBC", "MCIGAM"};
String[] str = new String[input.Length];
int i;
for (i = 0; i < input.Length; ++i)
{
str[i] = input[i];
}
Console.WriteLine("count: " + GFG.searchString(needle, 0, 0, str, str.Length, str[0].Length).ToString());
}
}
// This code is contributed by mukulsomukesh
Javascript
// JavaScript code for finding count
// of string in a given 2D
// character array.
// Utility function to search
// complete string from any
// given index of 2d char array
function internalSearch(needle, row, col, hay, row_max, col_max, xx)
{
var found = 0;
if (row >= 0 && row <= row_max && col >= 0 && col <= col_max && xx < needle.length && needle.charAt(xx) == hay[row].charAt(col))
{
var match = needle.charAt(xx);
xx += 1;
hay[row] = hay[row].substring(0,col) + "0" + hay[row].substring(col + 1);
if (xx == needle.length)
{
found = 1;
}
else
{
// Through Backtrack searching
// in every directions
found += internalSearch(needle, row, col + 1, hay, row_max, col_max, xx);
found += internalSearch(needle, row, col - 1, hay, row_max, col_max, xx);
found += internalSearch(needle, row + 1, col, hay, row_max, col_max, xx);
found += internalSearch(needle, row - 1, col, hay, row_max, col_max, xx);
}
hay[row] = hay[row].substring(0,col) + match + hay[row].substring(col + 1);
}
return found;
}
// Function to search the string in 2d array
function searchString(needle, row, col, str, row_count, col_count)
{
var found = 0;
var r = 0;
var c = 0;
for (r = 0; r < row_count; ++r)
{
for (c = 0; c < col_count; ++c)
{
found += internalSearch(needle, r, c, str, row_count - 1, col_count - 1, 0);
}
}
return found;
}
// Driver code
var needle = "MAGIC";
var input = ["BBABBM", "CBMBBA", "IBABBG", "GOZBBI", "ABBBBC", "MCIGAM"];
var str = Array(input.length).fill(null);
var i = 0;
for (i = 0; i < input.length; ++i)
{
str[i] = input[i];
}
console.log("count: " + searchString(needle, 0, 0, str, str.length, str[0].length));
// This code is contributed by Aarti_Rathi
Producción
count: 3
Complejidad de tiempo: O(n*m), donde n es el tamaño de la fila y m es el tamaño de la columna.
Espacio Auxiliar: O(n*m)