Найти, можно ли получить строку из матрицы символов

Question

Учитывая матрицу символов и строку, найдите, может ли строка быть получена из матрицы. От каждого символа в матрице мы можем двигаться вверх / вниз / вправо / влево. Например, если матрица [3][4] имеет вид:

o f a s
l l q w
z o w k 

и строка follow, тогда функция должна вернуть true.

Единственный подход, который я могу придумать, - это алгоритм обратного отслеживания, который ищет, возможно ли слово или нет. Есть ли другой более быстрый алгоритм для решения этой проблемы?

И, предположим, у меня много запросов (при поиске того, существует слово или нет). Тогда можно ли выполнить некоторую предварительную обработку, чтобы быстрее отвечать на запросы?

Answer 1

Вы можете решить это с помощью DFS. Давайте определим график для проблемы. Вершины графа будут состоять из ячейки комбинации ячейки матрицы и длины префикса искомой строки. Когда мы находимся в заданной вершине, это будет означать, что все символы указанного префикса до сих пор были сопоставлены и что мы в настоящее время находимся в данной ячейке.

Мы определяем ребра как соединяющие ячейки, граничащие со стороной и выполняющие "действительную" транзакцию Именно эта ячейка должна быть следующей в строке, которую мы ищем.

Чтобы решить эту проблему, мы делаем DFS из всех ячеек, которые содержат первую букву строки и префикс длины 1(то есть мы сопоставили эту первую букву). После этого мы продолжаем поиск и на каждом шаге вычисляем, какие ребра выходят из текущей позиции (комбинация длины префикса ячейки / строки). Мы завершаем первый раз, когда мы достигаем префикса длины L - длина строки.

Обратите внимание, что DFS может считаться возвращением назад, но что более важно, это отслеживать узлы на графике, который мы уже посетили. Таким образом, общая сложность связана с N * M * L где N а также M Размеры матрицы и L - длина строки.

Answer 2

Конечно, вы можете найти все возможные строки (начните с символа и идите как можно дальше). Это можно сделать с помощью рекурсивной функции.

сетка:

abc
def
ghi

строки:

abcfedghi
abcfehgd
abcfehi
abedghif
abefc
abefighd
abehgd
abehifc
ad...
...

Затем сортируйте эти строки и при поиске слова используйте двоичный поиск в списке. (При поиске n буквенного слова вы, конечно, учитываете только первые n букв строк в списке.) Требуется много подготовки и много памяти, но поиск будет быстрым. Так что, если вы используете одну и ту же сетку снова и снова, подготовка может в конечном итоге окупиться:-)

Answer 3

Ниже приведен псевдокод для определения наличия заданной строки в данной матрице. Здесь посещенные отслеживает местоположение строки в матрице и использует отслеживание для отслеживания этого. Я надеюсь, что это полезно.

bool isSafe(matrix[n][m], int visited[n][m], int i, int j, int n, int m){

if(i<m && j<n && i>=0 && j>=0 && visited[i][j] == 0)
    return true;
return false;
}

bool dfs(char matrix[n][m], int i, int j, int visited[n][m], char str[], int index){

if(index == strlen(str))
    return true;

// row moves
int x[] = {-1, 0, 1, -1};
// col moves
int y[] = {0, -1, 1, 0};

if(str[index] == matrix[i][j]){
    visited[i][j] = 1;
    // for all the neighbours
    for(int k = 0; k<4; k++){
        // mark given position visited
        next_x = i + x[k];
        next_y = j + y[k];

        if(isSafe(matrix, visited, next_x, next_y, n, m)){
            if(dfs(matrix, next_x, next_y, visited, str, index+1) == true)
                return true;
        }
    }
    // backtrack
    visited[i][j] = 0;

}

return false;

}

bool isPresent(char matrix[n][m], char str[]){

// visited initialized to 0
int visited[n][m] = {0};

for(int i=0;i<n;i++)
    for(int j=0;j<n;j++){
        if(dfs(matrix, i, j, n, m ,visited, str, 0) == true)
            return true;
    }


return false;
}