Recuento del número de strings dadas en una array de caracteres 2D

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)

Publicación traducida automáticamente

Artículo escrito por yasinj3 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *