## Problem: Word Boggle

*Difficulty: Medium

Given a dictionary, a method to do lookup in dictionary and a M x N board where every cell has one character. Find all possible words that can be formed by a sequence of adjacent characters. Note that we can move to any of 8 adjacent characters, but a word should not have multiple instances of same cell.

Example:

Input: dictionary[] = {"GEEKS", "FOR", "QUIZ", "GO"}; boggle[][] = {{'G','I','Z'}, {'U','E','K'}, {'Q','S','E'}}; Output: Following words of dictionary are present GEEKS, QUIZ

**Input:**

The first line of input contains an integer T denoting the no of test cases . Then T test cases follow. Each test case contains an integer x denoting the no of words in the dictionary. Then in the next line are x space separated strings denoting the contents of the dictinory. In the next line are two integers N and M denoting the size of the boggle. The last line of each test case contains NxM space separated values of the boggle.

**Output:**

For each test case in a new line print the space separated sorted distinct words of the dictionary which could be formed from the boggle. If no word can be formed print -1.

**Constraints:**

1<=T<=10

1<=x<=10

1<=n,m<=7

**Example:
Input:**

1

4

GEEKS FOR QUIZ GO

3 3

G I Z U E K Q S E

**Output:**

GEEKS QUIZ

*Approach: This problem is almost the same with this.

The mechanism gonna be used here is back tracking. There are only two main parts in the algorithm:

- With each cell in boggle matrix (two for loops)
- Check all possible words that can be generated with that cell
- While generating, if a generated word can be found in dictionary, add to result
- if the length of generated word equal the length of longest word in dictionary, return (base case)

- After getting all words, put them into a set to eliminate duplicate words, then sorted them alphabetically before output

Suppose max_level is the length of longest word in dictionary, as soon as the length of a generated word exceeds max_level, we return. Why? Because if we still continue generating, there is no word will match anything in dictionary.

Implementation: Python 2.7

from __future__ import print_function def generate_words(x, y, dictionary, boggle, visited_cells, level, max_level, result, word): visited_cells.append((x, y)) word += boggle[x][y] #print word if word in dictionary: result.append(word) eight_directions = ((x+1, y), (x-1, y), (x, y+1), (x, y-1), (x+1, y+1), (x+1, y-1), (x-1, y+1), (x-1, y-1)) eight_directions = [(new_x,new_y) for new_x,new_y in eight_directions if in_bound(new_x, new_y, boggle) and (new_x, new_y) not in visited_cells] if level > max_level: return for new_x, new_y in eight_directions: generate_words(new_x, new_y, dictionary, boggle, visited_cells, level+1, max_level, result, word) visited_cells.pop() def find_all_possible_words(dictionary, boggle): max_level = get_max_level(dictionary) overall_result = [] for x in xrange(len(boggle)): for y in xrange(len(boggle[x])): result = [] visited_cells = [] level = 0 word = "" generate_words(x, y, dictionary, boggle, visited_cells, level, max_level, result, word) if result: overall_result.extend(result) overall_result = set(overall_result) overall_result = list(sorted(overall_result)) if overall_result: print(*overall_result, sep=" ") else: print(-1) def get_max_level(dictionary): return max(len(x) for x in dictionary) def in_bound(x, y, boggle): return (x >= 0 and x < len(boggle)) and (y >= 0 and y < (len(boggle[0]))) if __name__ == '__main__': t = input() for _ in range(t): n = input() dictionary = raw_input().strip().split() n, m = map(int, raw_input().strip().split()) boggle = [] temp = raw_input().strip().split() for i in range(0, len(temp), m): boggle.append(temp[i:i+m]) #print(dictionary) #print(boggle) find_all_possible_words(dictionary, boggle)

## Reply