Algorithms and Data Structures

Pathword Quest

You are given an n x n grid of lowercase English letters. Your task is to determine whether there is a simple path in this grid that can be read as the given string s.
A simple path starts from any cell in the grid and moves to an adjacent cell (up, down, left, or right) in each step. The path can only visit each cell once and can change direction as needed.
The letters in the path must form the string s when read in order.


The first line contains an integer n (1 ≀ n ≀ 6), representing the size of the grid.
The next n lines contain n lowercase English letters each, representing the letters in each cell of the grid.
The last line contains a string s (1 ≀ |s| ≀ 15), consisting of lowercase English letters.


Print YES if there is a simple path in the grid that forms the string s when read in order. Otherwise, print NO.


3 a b e d c f g h i abc
3 a b e d c f g h i abce


Time limit: 0.2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue