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
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)