Рубрики

Поиск слова в 2D сетке символов

Матрицы, Поиск по шаблону

По заданной двумерной сетке символов и слова найдите все вхождения данного слова в сетке. Слово может быть найдено во всех 8 направлениях в любой точке. Говорят, слово можно найти в направлении, если все символы совпадают в этом направлении (не в зигзагообразной форме).

8 направлений: горизонтально влево, горизонтально вправо, вертикально вверх и 4 диагональных направления.

Пример:

Input:  grid[][] = {"GEEKSFORGEEKS",
                    "GEEKSQUIZGEEK",
                    "IDEQAPRACTICE"};
        word = "GEEKS"

Output: pattern found at 0, 0
        pattern found at 0, 8
        pattern found at 1, 0

Input:  grid[][] = {"GEEKSFORGEEKS",
                    "GEEKSQUIZGEEK",
                    "IDEQAPRACTICE"};
        word = "EEE"

Output: pattern found at 0, 2
        pattern found at 0, 10
        pattern found at 2, 2
        pattern found at 2, 12

Ниже на диаграмме показана увеличенная сетка и наличие в ней разных слов.

Источник: Microsoft Интервью Вопрос

Идея, используемая здесь, проста, мы проверяем каждую ячейку. Если ячейка имеет первый символ, то мы один за другим пробуем все 8 направлений из этой ячейки на совпадение. Реализация интересная, хотя. Мы используем два массива x [] и y [], чтобы найти следующий ход во всех 8 направлениях.

Ниже приведена реализация того же.

C ++

// C ++ программы для поиска слова в 2D сетке
#include<bits/stdc++.h>

using namespace std;

  
// Строки и столбцы в данной сетке
#define R 3
#define C 14

  
// Для поиска по всем 8 направлениям

int x[] = { -1, -1, -1, 0, 0, 1, 1, 1 };

int y[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

  
// Эта функция ищет во всех 8 направлениях от точки
// (строка, столбец) в сетке [] []

bool search2D(char grid[R][C], int row, int col, string word)

{

    // Если первый символ слова не совпадает с

    // заданная отправная точка в сетке.

    if (grid[row][col] != word[0])

      return false;

  

    int len = word.length();

  

    // Поиск слова по всем 8 направлениям, начиная с (row, col)

    for (int dir = 0; dir < 8; dir++)

    {

        // Инициализация начальной точки для текущего направления

        int k, rd = row + x[dir], cd = col + y[dir];

  

        // Первый символ уже проверен, совпадение осталось

        // персонажи

        for (k = 1; k < len; k++)

        {

            // Если перерыв

            if (rd >= R || rd < 0 || cd >= C || cd < 0)

                break;

  

            // Если не совпадает, перерыв

            if (grid[rd][cd] != word[k])

                break;

  

            // Движение в определенном направлении

            rd += x[dir], cd += y[dir];

        }

  

        // Если все символы совпадают, то значение must

        // быть равным длине слова

        if (k == len)

            return true;

    }

    return false;

}

  
// Поиск заданного слова в заданной матрице во всех 8 направлениях

void patternSearch(char grid[R][C], string word)

{

    // Рассмотрим каждую точку как отправную точку и поиск

    // данное слово

    for (int row = 0; row < R; row++)

       for (int col = 0; col < C; col++)

          if (search2D(grid, row, col, word))

             cout << "pattern found at " << row << ", "

                  << col << endl;

}

  
// Драйвер программы

int main()

{

    char grid[R][C] = {"GEEKSFORGEEKS",

                       "GEEKSQUIZGEEK",

                       "IDEQAPRACTICE"

                      };

  

    patternSearch(grid, "GEEKS");

    cout << endl; 

    patternSearch(grid, "EEE");

    return 0;

}

Джава

// Java программа для поиска слова в 2D сетке

import java.io.*;

import java.util.*;

  

class GFG 

{

  

    // Строки и столбцы в данной сетке

    static int R, C;

  

    // Для поиска по всем 8 направлениям

    static int[] x = { -1, -1, -1, 0, 0, 1, 1, 1 }; 

    static int[] y = { -1, 0, 1, -1, 1, -1, 0, 1 }; 

  

    // Эта функция ищет во всех 8 направлениях от точки

    // (строка, столбец) в сетке [] []

    static boolean search2D(char[][] grid, int row,

                            int col, String word)

    {

            // Если первый символ слова не совпадает с

            // заданная отправная точка в сетке.

            if (grid[row][col] != word.charAt(0))

                return false;

  

            int len = word.length();

              

            // Поиск слова по всем 8 направлениям

            // начиная с (row, col)

            for (int dir = 0; dir < 8; dir++)

            {

                // Инициализация начальной точки

                // для текущего направления

                int k, rd = row + x[dir], cd = col + y[dir];

  

                // Первый символ уже проверен,

                // сопоставляем оставшиеся символы

                for (k = 1; k < len; k++)

                {

                    // Если перерыв

                    if (rd >= R || rd < 0 || cd >= C || cd < 0)

                        break;

  

                    // Если не совпадает, перерыв

                    if (grid[rd][cd] != word.charAt(k))

                        break;

  

                    // Движение в определенном направлении

                    rd += x[dir];

                    cd += y[dir];

                } 

  

                // Если все символы совпадают, то значение must

                // быть равным длине слова

                if (k == len)

                    return true; 

            }

        return false;

    }

  

    // Поиск заданного слова в заданном

    // матрица во всех 8 направлениях

    static void patternSearch(char[][] grid, String word)

    {

            // Рассматривать каждую точку как начальную

            // указать и найти данное слово

            for (int row = 0; row < R; row++) 

            {

                for (int col = 0; col < C; col++) 

                {

                    if (search2D(grid, row, col, word))

                        System.out.println("pattern found at " + row + 

                                                            ", " + col);

                }

            }

    }

  

    // Код драйвера

    public static void main(String args[])

    {

            R = 3;

            C = 13;

            char[][] grid = {{'G','E','E','K','S','F','O','R','G','E','E','K','S'},

                                {'G','E','E','K','S','Q','U','I','Z','G','E','E','K'},

                                {'I','D','E','Q','A','P','R','A','C','T','I','C','E'}};

            patternSearch(grid, "GEEKS");

            System.out.println();

            patternSearch(grid, "EEE");

    }

} 

  
// Этот код предоставлен rachana soma

C #

// C # программа для поиска слова в 2D сетке

using System;

class GFG 

{

  

    // Строки и столбцы в данной сетке

    static int R, C;

  

    // Для поиска по всем 8 направлениям

    static int[] x = {-1, -1, -1, 0, 0, 1, 1, 1};

    static int[] y = {-1, 0, 1, -1, 1, -1, 0, 1};

  

    // Эта функция ищет во всех 8 направлениях

    // из точки (строки, столбца) в сетке [,]

    static bool search2D(char[,] grid, int row,

                         int col, String word) 

    {

        // Если первый символ слова не совпадает

        // с заданной начальной точкой в сетке.

        if (grid[row,col] != word[0])

        {

            return false;

        }

  

        int len = word.Length;

  

        // Поиск слова по всем 8 направлениям

        // начиная с (row, col)

        for (int dir = 0; dir < 8; dir++) 

        {

            // Инициализация начальной точки

            // для текущего направления

            int k, rd = row + x[dir], cd = col + y[dir];

  

            // Первый символ уже проверен,

            // сопоставляем оставшиеся символы

            for (k = 1; k < len; k++) 

            {

                // Если перерыв

                if (rd >= R || rd < 0 || cd >= C || cd < 0)

                {

                    break;

                }

  

                // Если не совпадает, перерыв

                if (grid[rd, cd] != word[k])

                {

                    break;

                }

  

                // Движение в определенном направлении

                rd += x[dir];

                cd += y[dir];

            }

  

            // Если все символы совпадают, то значение k

            // должно быть равно длине слова

            if (k == len) 

            {

                return true;

            }

        }

        return false;

    }

  

    // Поиск заданного слова в заданном

    // матрица во всех 8 направлениях

    static void patternSearch(char[,] grid, 

                              String word)

    {

        // Рассматривать каждую точку как начальную

        // указать и найти данное слово

        for (int row = 0; row < R; row++)

        {

            for (int col = 0; col < C; col++)

            {

                if (search2D(grid, row, col, word))

                {

                    Console.WriteLine("pattern found at " + 

                                         row + ", " + col);

                }

            }

        }

    }

  

    // Код драйвера

    public static void Main(String []args) 

    {

        R = 3;

        C = 13;

        char[,] grid = {{'G', 'E', 'E', 'K', 'S', 'F', 'O',

                         'R', 'G', 'E', 'E', 'K', 'S'},

                        {'G', 'E', 'E', 'K', 'S', 'Q', 'U', 

                         'I', 'Z', 'G', 'E', 'E', 'K'},

                        {'I', 'D', 'E', 'Q', 'A', 'P', 'R', 

                         'A', 'C', 'T', 'I', 'C', 'E'}};

        patternSearch(grid, "GEEKS");

        Console.WriteLine();

        patternSearch(grid, "EEE");

    }

} 

  
// Этот код предоставлен Rajput-Ji


Выход:

pattern found at 0, 0
pattern found at 0, 8
pattern found at 1, 0

pattern found at 0, 2
pattern found at 0, 10
pattern found at 2, 2
pattern found at 2, 12

Упражнение: Приведенное выше решение печатает только места слова. Расширьте его, чтобы напечатать направление, в котором присутствует слово.

Смотрите это для решения упражнений.

Эта статья предоставлена Уткаршем Триведи . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Поиск слова в 2D сетке символов

0.00 (0%) 0 votes