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)

 

 

Advertisements