Facebook Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
Well written code. Here is a cake for c++ enthusiasts, which handles multiple starting points for a given search string.
#include <iostream>
#include <deque>
#include <map>
#include <list>
#include <string>
#define rep(i,m) for(int i=0;i<(int)(m);i++)
#define rep2(i,n,m) for(int i=n;i<(int)(m);i++)
using namespace std;
void PreprocessBoard(string boggleBoard, map<char, list<int> > &prePosMap) {
rep(i,boggleBoard.size())
prePosMap[boggleBoard[i]].push_back(i);
}
void GetNeighbours(string boggleBoard,int curPosDst, map<int,bool> &neighboursMap, map<int,bool> &resultPosMap, int wd, int ht) {
neighboursMap.clear();
int posx = curPosDst/wd, posy = curPosDst%ht;
rep2(i,posx-1,posx+2)
rep2(j,posy-1,posy+2) {
if( (i>=0) && (j>=0) && (i < wd) && (j < ht) && (resultPosMap.find(i*wd+j) == resultPosMap.end()) ) {
neighboursMap[i*wd+j] = 1;
}
}
}
bool _SearchBoggle(string boggleBoard, string searchStr, map<int,bool> &resultPosMap ,deque<int> &resultPosQ, int curPosSrc, int wd, int ht )
{
if( curPosSrc == searchStr.size() )
return true;
int prevPosDst = resultPosQ.back();
map<int,bool> neighboursMap;
GetNeighbours(boggleBoard, prevPosDst, neighboursMap, resultPosMap, wd, ht);
for(map<int,bool>::iterator it = neighboursMap.begin(); it!=neighboursMap.end(); it++ ) {
if( boggleBoard[it->first] == searchStr[curPosSrc] ) {
resultPosMap[it->first] = 1;
resultPosQ.push_back(it->first);
if( _SearchBoggle(boggleBoard, searchStr, resultPosMap ,resultPosQ, curPosSrc+1, wd, ht ) ) {
return true;
}
else {
// Backtrack :)
resultPosMap.erase(it->first);
resultPosQ.pop_back();
}
}
}
return false;
}
bool SearchBoggle(string boggleBoard, map<char, list<int> > &prePosMap, string searchStr, deque<int> &resultPosQ, int wd, int ht) {
// resultPos contains the positions of the result.
if( searchStr.size() == 0 )
return false;
map<char, list<int> >::iterator it = prePosMap.find(searchStr[0]);
if( it == prePosMap.end() )
return false;
list<int> startingPositions = it->second;
for(list<int>::iterator it = startingPositions.begin(); it!=startingPositions.end(); it++ ) {
resultPosQ.clear();
map<int,bool> resultPosMap; resultPosMap.clear();
resultPosMap[*it] = 1;
resultPosQ.push_back(*it);
if( _SearchBoggle(boggleBoard, searchStr, resultPosMap, resultPosQ, 1, wd, ht) )
return true;
}
return false;
}
int main()
{
string boggleBoard = "SMEFRATDLONIKAFB";
int width = 4, height = 4;
map<char, list<int> > prePosMap;
deque<int> resultPos;
PreprocessBoard(boggleBoard, prePosMap);
bool isStringPresent;
isStringPresent = SearchBoggle(boggleBoard, prePosMap, "STAR", resultPos, width, height);
isStringPresent = SearchBoggle(boggleBoard, prePosMap, "TONE", resultPos, width, height);
isStringPresent = SearchBoggle(boggleBoard, prePosMap, "NOTE", resultPos, width, height);
isStringPresent = SearchBoggle(boggleBoard, prePosMap, "SAND", resultPos, width, height);
return 0;
}
Heres a DFS implementation with a hash lookup for the first letter written in objective-c
#import <Foundation/Foundation.h>
@interface Node : NSObject
@property (nonatomic, strong) NSString * letter;
@property (nonatomic, strong) NSMutableSet * adjacentNodes;
@end
@implementation Node
-(NSMutableSet *)adjacentNodes{
if(_adjacentNodes){
return _adjacentNodes;
}
_adjacentNodes = [[NSMutableSet alloc] init];
return _adjacentNodes;
}
@end
@interface Graph : NSObject
@property (nonatomic, strong) NSSet * nodes;
@property (nonatomic, strong) NSDictionary * lookupDictionary;
+(instancetype)graphForBoggleBoard:(NSArray *)board;
-(BOOL)searchForWord:(NSString *)word;
@end
@implementation Graph
+(instancetype)graphForBoggleBoard:(NSArray *)board{
NSMutableSet * nodes = [[NSMutableSet alloc] init];
NSMutableDictionary * dictionary = [NSMutableDictionary dictionary];
NSMutableArray * nodeBoard = [[NSMutableArray alloc] initWithCapacity:board.count];
for (NSArray * row in board){
NSMutableArray * nodeRow = [[NSMutableArray alloc] initWithCapacity:row.count];
for (NSString * letter in row){
Node * node = [[Node alloc] init];
node.letter = letter;
[nodeRow addObject:node];
[nodes addObject:node];
if (dictionary[node.letter]){
[dictionary[node.letter] addObject:node];
}else{
dictionary[node.letter] = @[node].mutableCopy;
}
}
[nodeBoard addObject:nodeRow];
}
NSArray * previousRow = nil;
for (NSInteger row = 0; row < nodeBoard.count; row++){
NSArray * nodeRow = nodeBoard[row];
for (NSInteger col = 0; col < nodeRow.count; col ++){
Node * currentNode = nodeBoard[row][col];
for (Node * node in previousRow){
[currentNode.adjacentNodes addObject:node];
[node.adjacentNodes addObject:currentNode];
}
if (col > 0){
Node * node = nodeBoard[row][col - 1];
[currentNode.adjacentNodes addObject:node];
[node.adjacentNodes addObject:currentNode];
}
}
previousRow = nodeRow;
}
Graph * graph = [[Graph alloc] init];
graph.lookupDictionary = dictionary;
graph.nodes = nodes;
return graph;
}
BOOL depthFirstSearch(Node * node, NSString * word, NSInteger depth, NSMutableSet * visitedNodes){
unichar nodeLetter = [node.letter characterAtIndex:0];
unichar wordLetter = [word characterAtIndex:depth];
[visitedNodes addObject:node];
if (nodeLetter == wordLetter){
if (depth < word.length - 1) {
for (Node * adjacentNode in node.adjacentNodes){
if ([visitedNodes containsObject:adjacentNode]) continue;
BOOL found = depthFirstSearch(adjacentNode, word, depth + 1, visitedNodes);
if (found == YES) return found;
}
}
else return YES;
}
[visitedNodes removeObject:node];
return NO;
}
-(BOOL)searchForWord:(NSString *)word{
NSString * firstLetter = [NSString stringWithFormat:@"%c",[word characterAtIndex:0]];
NSSet * firstNodes = self.lookupDictionary[firstLetter];
for (Node * node in firstNodes){
NSMutableSet * visitedNodes = [[NSMutableSet alloc] initWithCapacity:word.length];
BOOL found = depthFirstSearch(node, word, 0, visitedNodes);
if (found == YES) return YES;
}
return NO;
}
@end
int main(int argc, char *argv[]) {
@autoreleasepool {
NSArray * boggleBoard = @[
@[@"a", @"b", @"c"],
@[@"d", @"d", @"h"],
@[@"e", @"i", @"u"]
];
Graph * graph = [Graph graphForBoggleBoard:boggleBoard];
NSLog (@"Word %@", [graph searchForWord:@"chuddd"] ? @"exists" : @"doesnt exist");
}
return 0;
}
We need to build a hash for each character in the boggle board, and make a recursive search on each character of the string:
bbr1=['S', 'M', 'E','F'];
bbr2=['R', 'A', 'T','D'];
bbr3=['L', 'O', 'N','I'];
bbr4=['K', 'A', 'F','B'];
bb=[bbr1, bbr2, bbr3,bbr4];
rowmax=len(bb);
colmax=len(bb[0]);
wordPos={};
for row in range(4):
for col in range(4):
if bb[row][col] in wordPos.keys():
wordPos[bb[row][col]].append([row, col]);
else:
wordPos[bb[row][col]]=[[row,col]];
print wordPos;
print range(-1,1);
def searchWord(pos, curPos, wordList):
print curPos, wordList;
if len(wordList)==0:
return 0;
if curPos == None:
if wordList[0] in pos.keys():
return searchWord(wordPos, pos[wordList[0]], wordList[1:]);
else:
return -1;
else:
for onePos in curPos:
for h in range(-1,2):
for v in range(-1,2):
if h==0 and v==0:
continue;
row=onePos[0]+v;
col=onePos[1]+h;
if row < 0 or row > rowmax-1:
continue;
if col < 0 or col > colmax-1:
continue;
if bb[row][col] == wordList[0]:
if 0==searchWord(pos,[[row, col]], wordList[1:]):
return 0;
return -1;
print searchWord(wordPos, None, "STAR");
print searchWord(wordPos, None, "TONE");
print searchWord(wordPos, None, "NOTE");
print searchWord(wordPos, None, "SAND");
print searchWord(wordPos, None, "AFB");
print searchWord(wordPos, None, "UU");
print searchWord(wordPos, None, "");
I think this is the same idea as chenic626, but I couldn't understand their code very well, so I did it myself.
import collections
def pathExists(current_coordinate, coordinates_available, letters):
# This is our base case. If there are no letters left to check, then we
# have successfully matched all the ones we wanted.
if not letters:
return True
current_letter = letters[0]
if current_letter not in coordinates_available:
return False
(current_row, current_col) = current_coordinate
for (row_index, col_index) in coordinates_available[current_letter]:
# If the next letter has a co-ordinate within one cells radius, continue
# our search through it.
if ( abs(row_index - current_row) <= 1
and abs(col_index - current_col) <= 1 ):
if pathExists((row_index, col_index),
coordinates_available,
letters[1:]):
return True
return False
def isWordInMatrix(matrix, word):
# Create a map of letter => co-ordinate positions, noting that any given
# letter may be in more than one cell in our grid.
coordinates = collections.defaultdict(list)
for row_index, row in enumerate(matrix):
for col_index, letter in enumerate(row):
coordinates[letter].append( (row_index, col_index) )
# For each letter, pull up all the co-ordinates needed to construct it
# (they're the ones we have to work with, so we call them the available
# ones.)
coordinates_available = {}
for letter in word:
coordinates_available[letter] = coordinates[letter]
# We start our search with the first letter of the word.
startingCoordinates = coordinates_available[word[0]]
for coordinate in startingCoordinates:
if pathExists(coordinate, coordinates_available, word[1:]):
return True
return False
# Tests.
matrix = [ [ 'S', 'M', 'E', 'F' ],
[ 'R', 'A', 'T', 'D' ],
[ 'L', 'O', 'N', 'I' ],
[ 'K', 'A', 'F', 'S' ] ]
assert isWordInMatrix(matrix, 'SAND')
assert isWordInMatrix(matrix, 'NOTE')
assert not isWordInMatrix(matrix, 'STAR')
assert not isWordInMatrix(matrix, 'TONE')
assert isWordInMatrix(matrix, 'S')
assert isWordInMatrix(matrix, 'SRLKAFSIDFEMATNO')
assert not isWordInMatrix(matrix, 'SANSFAKFDI')
Build a hash map keyed on position. For every letter of the word you have to find, search every adjacent position of the previous letter. For the first letter, you will have to search all positions.
This does it in O(n). Please correct me if I am wrong.
For an nxn grid, it's not possible to do it in O(n), O(n^2) is minimal.
I don't understand why you're building a hashmap? Arrays are O(1) anyway, which is what your input grid will be.
HashMap is the best solution, having O(n). Add all the characters as keys. Now get the string, take each letter from string and search in HashMap.
All you have managed to do is verify all the letters are in the word in O(n). You have *not* shown that there is a path (by traversing adjacent cells).
Your idea would say "TONE" is OK because all the letters are in the HashMap, which is incorrect, "TONE" is not a valid word (as given in the question).
@rfaccone
Can you please clarify how is NOTE - Yes and TONE - No as I could see all the four chars in the two words same?
This doesn't handle the duplicate characters.If someone can suggest a way to handle that ?
#include <stdio.h>
#include <string.h>
#define SIZE 4
#define CHAR_SIZE 256
struct co{
int i;
int j;
};
struct c_r{
struct co s[CHAR_SIZE];
char track[CHAR_SIZE];
};
struct c_r main_;
int search(char mat[SIZE][SIZE], char c, int i, int j)
{
/* search in top if it exists */
if(i-1 >= 0)
if(mat[i-1][j] == c)
return 1;
/* search in top right if it exists */
if(i-1 >= 0 && j+1 < SIZE)
if(mat[i-1][j+1] == c)
return 1;
/* search in top left if it exists */
if(i-1 >= 0 && j-1 >= 0)
if(mat[i-1][j-1] == c)
return 1;
/* search in current down if it exists */
if(i+1 < SIZE)
if(mat[i+1][j] == c)
return 1;
/* search in current left if it exists */
if(j-1 >= 0)
if(mat[i][j-1] == c)
return 1;
/* search in current right if it exists */
if(j+1 < SIZE)
if(mat[i][j+1] == c)
return 1;
/* search in down left if it exists */
if(i+1 < SIZE && j-1 >= 0)
if(mat[i+1][j-1] == c)
return 1;
/* search in down right if it exists */
if(i+1 < SIZE && j+1 < SIZE)
if(mat[i+1][j+1] == c)
return 1;
return 0;
}
int find_word(char mat[SIZE][SIZE], char *word, int i, int size)
{
if(i >= size)
return 1;
if(main_.track[word[i] -'0'] == word[i]){
if(i+1 >= size)
return 1;
if(search(mat, word[i+1], main_.s[main_.track[word[i] -'0'] - '0'].i, main_.s[main_.track[word[i] -'0'] - '0'].j)) {
find_word(mat, word, i+1, size);
} else {
return 0;
}
} else {
return 0;
}
}
int main()
{
int i, j;
char *word = {"TDIN"};
char mat[SIZE][SIZE] = {
'S', 'M', 'E', 'F',
'R', 'A', 'T', 'D',
'L', 'O', 'N', 'I',
'K', 'Z', 'P', 'B',
};
for(i=0;i<SIZE;i++) {
for(j=0;j<SIZE;j++) {
main_.track[mat[i][j] - '0'] = mat[i][j];
main_.s[mat[i][j] - '0'].i = i;
main_.s[mat[i][j] - '0'].j = j;
}
}
if(find_word(mat, word, 0, strlen(word)))
printf("found\n");
else
printf("not found\n");
return 0;
}
findWord(int[][] data,char[] word){
int k=0;//position of character in checking word.
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(data[i][j]==word[k]){
if(checkWord(i,j,k++,data,words){
System.out.println("word exists");
break;
}
}
}
}
}
public boolean checkWord(int i,int j,int k,int[][] data,char[] word){
if(k==words.length) return true;
char letter=words[k];
if(j!=3 && data[i][j+1]==letter) return checkWord(i,j++,k++,data,word);
if(i!=3 && data[i+1][j]==letter) return checkWord(i++,j,k++,data,word);
if(i!=3 && j!=3 && data[i+1][j+1]==letter) return checkWord(i++,j++,k++,data,word);
if(i!=0 && data[i-1][j]==letter) return checkWord(i--,j,k++,data,word);
if(j!=0 && data[i][j-1]==letter) return checkWord(i,j--,k++,data,word);
if(i!=0 && j!=0 && data[i-1][j-1]==letter) return checkWord(i--,j--,k++,data,word);
if(i!=3 && j!=0 && data[i+1][j-1]==letter) return checkWord(i++,j--,k++,data,word);
if(i!=0 && j!=3 && data[i-1][j+1]==letter) return checkWord(i--,j++,k++,data,word);
}
time complexiy is O(N*M*K) in worst case, where N is number of rows, M is number of columns and K is length of word for which we are searching. Please let me know for improvements since I used brute force technique here
public String verifyWords(String word){
char[] a={'S','M','E','F'};
char[] b={'R','A','T','D'};
char[] c={'L','O','N','I'};
char[] d={'K','A','F','B'};
int count=0;
for (int i = 0; i < word.length(); i++) {
char my=word.charAt(i);
for (int j = 0; j < a.length; j++) {
if(my==a[j]){
count=count+1;
}
}
for (int k = 0; k < b.length; k++) {
if(my==b[k]){
count=count+1;
}
} for (int L = 0; L < c.length; L++) {
if(my==c[L]){
count=count+1;
}
}
for (int M = 0; M < d.length; M++) {
if(my==d[M]){
count=count+1;
}
}
}
System.out.println("count is--->"+count);
if(count>=4){
return "Yes";
}
else{
return "NO";
}
}
Here is the answer in C#. This generalize into any size word and and size board (dimension mxn)
sealed class Program
{
static void Main(string[] args)
{
//S M E F
//R A T D
//L O N I
//K A F B
char[,] board = new char[4, 4];
board[0, 0] = 's'; board[0, 1] = 'm'; board[0, 2] = 'e'; board[0, 3] = 'f';
board[1, 0] = 'r'; board[1, 1] = 'a'; board[1, 2] = 't'; board[1, 3] = 'd';
board[2, 0] = 'l'; board[2, 1] = 'o'; board[2, 2] = 'n'; board[2, 3] = 'i';
board[3, 0] = 'k'; board[3, 1] = 'a'; board[3, 2] = 'f'; board[3, 3] = 'b';
string word = "sand";
bool value = search(board, word);
}
static bool search(char[,] board, string word)
{
for (int i = 0; i < board.GetLength(0); i++)
{
for (int j = 0; j < board.GetLength(1); j++)
{
if (find(i, j, board, word))
{
return true;
}
}
}
return false;
}
static bool find(int i, int j, char[,] board, string word)
{
if (word.Length == 1)
{
return board[i, j] == word[0];
}
bool v0=false,v1=false, v2=false, v3=false, v4=false, v5=false, v6=false, v7=false, v8=false;
int m = board.GetLength(0);
int n = board.GetLength(1);
string part = word.Substring(1, word.Length - 1);
v0 = board[i, j] == word[0];
// Search the neighbourhood
if (i > 0) { v1 = find(i - 1, j, board, part); }
if (i > 0 && j < n - 1) { v2 = find(i - 1, j + 1, board, part); }
if (j < n - 1) { v3 = find(i, j + 1, board, part); }
if (i < m - 1 && j < n - 1) { v4 = find(i + 1, j + 1, board, part); }
if (i < m - 1) { v5 = find(i + 1, j, board, part); }
if (i < m - 1 && j > 0) { v6 = find(i + 1, j - 1, board, part); }
if (j > 0) { v7 = find(i, j - 1, board, part); }
if (i > 0 && j > 0) { v8 = find(i - 1, j - 1, board, part); }
return v0 &&( v1 || v2 || v3||v4||v5||v6||v7||v8);
}
}
Make a graph of 26 vertices and the edges representing the 8 neighbors. Note that some of the vertices would have more than 8 neighbors because the vertex character may be appearing multiple times.
Now perform BFS upto level 4 and stop when the word is found.
Wouldn't this lead to false positives? For example the word "FAME" would be found in such a graph, but it is not in the board.
How about representing the board as a graph (sixteen nodes with up to eight neighbours each), then searching for word by searching for the first letter, then doing a DFS from there. We could speed up the first letter search by constructing a MultiMap of letter->Nodes as we construct the graph.
<?php
$block = array('S', 'M', 'E', 'F',
'R', 'A', 'T', 'D',
'L', 'O', 'N', 'I',
'K', 'A', 'F', 'B');
$given_array = array("STAR", "TONE", "NOTE", "SAND");
foreach ($given_array as $given_str) {
echo '<br>';
$to_continue = FALSE;
$pos = NULL;
for ($j = 0; $j < strlen($given_str); $j++) {
if (isset($pos) && $to_continue === TRUE) {
$to_continue = false;
$l = $pos - 1;
$tl = $pos - 5;
$bl = $pos + 3;
$r = $pos + 1;
$tr = $pos - 3;
$br = $pos + 5;
$t = $pos - 4;
$b = $pos + 4;
$places = array('l' => $l, 'tl' => $tl, 'bl' => $bl, 'r' => $r, 'tr' => $tr, 'br' => $br, 't' => $t, 'b' => $b);
foreach ($places as $key => $place) {
if ($block[$place] == $given_str[$j]) {
$pos = $place;
$to_continue = TRUE;
break;
} else {
$to_continue = FALSE;
}
}
} else {
if ($j == 0) {
for ($i = 0; $i < count($block); $i++) {
if ($block[$i] == $given_str[$j]) {
$to_continue = TRUE;
$pos = $i;
break;
}
}
} else {
echo "$given_str: NOT FOUND";
break;
}
}
if ($j == (strlen($given_str) - 1 )) {
if ($to_continue) {
echo "$given_str: FOUND";
} else {
echo "$given_str: NOT FOUND";
}
}
}
}
I think we can build a trie from the board in o(n^4) which will make the search in o(n) for each query.
What do u think?
just use a hash-map:
#include<iostream.h>
#include<conio.h>
#include<string.h>
char hash[200], a[100][100], x[10];
void create_hash(char a)
{
if(hash[a]=='\0')
hash[a]=a;
}
void find_match()
{
int i, present=1;
for(i=0;i<strlen(x);i++)
{
if(x[i]!=hash[x[i]])
{
present=0;
break;
}
}
if(present==1)
cout<<"pattern present"<<endl;
else
cout<<"pattern not present"<<endl;
}
void create()
{
int r, c, i, j;
for(i=0;i<200;i++)
hash[i]=NULL;
cout<<"how many rows ? ";
cin>>r;
cout<<"how many cols ? ";
cin>>c;
cout<<"enter matrix:"<<endl;
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
cin>>a[i][j];
create_hash(a[i][j]);
}
}
cout<<"enter pattern: ";
cin>>x;
find_match();
}
main()
{
clrscr();
create();
getch();
}
Here is a solution, precompiling the boggle with a Trie and then doing the search in O(n).
import java.util.*;
import java.lang.*;
class Main
{
static String[]boggle=new String []{
"SMEF",
"RATD",
"LONI",
"KAFB"};
static String[]search=new String[]{
"STAR",
"TONE",
"NOTE",
"SAND"};
public static void main (String[] args) throws java.lang.Exception
{
Trie t = processBoggle(boggle);
for(String w: search){
System.out.println(w+":"+t.contains(w));
}
}
static Trie processBoggle(String[]boggle){
Trie t = new Trie();
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
dfs(i,j,boggle,"",t);
}
}
return t;
}
static boolean inBoard(int i,int j){
return i>=0 && i < 4 && j >= 0 && j < 4;
}
static void dfs(int i,int j, String[]boggle, String curr, Trie t){
if (!inBoard(i,j)) return;
if (visited[i][j]) return;
visited[i][j]=true;
curr = curr+boggle[i].charAt(j);
if (curr.length()==4){
t.insert(curr);
} else {
for(int d=0;d<8;d++){
dfs(i+dx[d],j+dy[d],boggle, curr, t);
}
}
visited[i][j]=false;
}
static boolean [][]visited=new boolean[4][4];
static int [] dx = new int[]{-1,-1,-1, 0,0, 1,1,1};
static int [] dy = new int[]{-1, 0, 1,-1,1,-1,0,1};
}
class Trie{
boolean isWord = false;
Trie [] children = new Trie[26];
boolean contains(String s){
if (s.length()==0){
return isWord;
} else {
int p = s.charAt(0)-'A';
return children[p]!=null && children[p].contains(s.substring(1));
}
}
void insert(String s){
if (s.length()==0){
isWord = true;
} else {
int p = s.charAt(0)-'A';
if (children[p]==null){
children[p] = new Trie();
}
children[p].insert(s.substring(1));
}
}
}
Here is a javascript solution that's a bit more readable and extensible, however it is slower than some of the other solutions.
var alphabet = 'smefratdlonikafb';
var BOARD = [];
var BOARD_ROWS = 4;
var BOARD_COLS = 4;
for(var i = 0; i < BOARD_COLS; i++) {
BOARD[i] = [];
for(var j = 0; j < BOARD_ROWS; j++) {
BOARD[i][j] = alphabet[0];
alphabet = alphabet.substring(1);
}
}
function getNearbyCells(x, y) {
var result = [];
if( x < BOARD_COLS-1) {
result.push({ x: x+1, y: y });
if( y < BOARD_ROWS-1 ) {
result.push({ x: x+1, y: y+1 });
}
if( y > 0 ) {
result.push({ x: x+1, y: y-1 });
}
}
if( x > 0 ) {
if( y < BOARD_ROWS-1) {
result.push({ x: x-1, y: y+1 });
}
result.push({ x: x-1, y: y });
if( y > 0 ) {
result.push({ x: x-1, y: y-1 });
}
}
if( y < BOARD_ROWS-1 ) {
result.push({ x: x, y: y+1 });
}
if( y > 0 ) {
result.push({ x: x, y: y-1 });
}
return result;
}
// Returns the location of the letter or false if it could not be found
function findLetter(x, y, l) {
var nearbyCells = getNearbyCells(x, y)
for( var i = 0; i < nearbyCells.length; i++ ) {
var position = nearbyCells[i];
if( BOARD[position.x][position.y] === l ) {
return {
x: position.x,
y: position.y
};
}
}
return false;
}
function searchForWord(x, y, word) {
var l = {x:x, y:y};
for( var i = 0; i < word.length; i++ ) {
var letter = word[i];
l = findLetter(l.x, l.y, letter);
if( !l ) {
return false;
}
}
return true;
}
function hasWord(word) {
// See if the first letter exists by searching the entire board
var firstLetter = word[0];
word = word.substring(1);
var possibleStartLocations = [];
for(var i = 0; i < BOARD_COLS; i++) {
for(var j = 0; j < BOARD_ROWS; j++) {
if(BOARD[i][j] === firstLetter) {
possibleStartLocations.push({
x: i,
y: j
});
}
}
}
// Starting from all the possible start locations, find the word
for( var i = 0; i < possibleStartLocations.length; i++ ) {
var p = possibleStartLocations[i];
var canFindWord = searchForWord(p.x, p.y, word);
if(canFindWord) {
return true;
}
}
return false;
}
Working PHP code
function boggle($word)
{
$bb = array(array('s', 'm', 'e', 'f'),
array('r', 'a', 't', 'd'),
array('l', 'o', 'n', 'i'),
array('k', 'a', 'f', 'b'));
$warr = str_split($word);
$k = 0;
for($i = 0; $i < count($bb[0]); $i++)
for($j = 0; $j < count($bb); $j++)
{
if($warr[0] == $bb[$i][$j])
{
$visited[$i][$j] = true;
return check($bb, $i, $j, $warr,0, $visited );
}
}
}
function check($bb,$i, $j, $warr, $curIndex, $visited)
{
print "$i, $j\n";
$n = 4;
$dx = array(0, 1, 1, 1, 0, -1, -1, -1);
$dy = array(1, 1, 0, -1, -1, -1, 0, 1);
if($curIndex == 3)
{
return true;
}
for($d = 0; $d<8; $d++)
{
$newi = $i + $dx[$d];
$newj = $j + $dy[$d];
if($newi >= 0 && $newi < $n && $newj >=0 && $newj < $n && !$visited[$newi][$newj]
&& $warr[$curIndex + 1] == $bb[$newi][$newj])
{
++$curIndex;
$visited[$newi][$newj] = true;
$ret = check($bb, $newi, $newj, $warr, $curIndex, $visited);
if($ret)
break;
--$curIndex;
$visited[$newi][$newj] = false;
print $curIndex;
print $warr[$curIndex];
print_r ($visited);
}
}
}
print boggle("smef);
Most solutions proposed here are overly complicated. This is just a simple recursion question. write a top down solution. if a character matches then try to match the next character in the 8 characters around.. here's a simple approch
char board[4][4] = { 'S', 'M', 'E', 'F',
'R', 'A', 'T', 'D',
'L', 'O', 'N', 'I',
'K', 'A', 'F', 'B' } ;
bool matchword(char*in, int x, int y)
{
bool match = false;
if (*in == '\0')
return true;
int newX;
int newY;
for ( int i = -1; i <=1; i++)
{
for (int j = -1; j <=1; j++)
{
newX = x+i;
newY = y+j;
if (newX < 0 || newX > 4) newX = x;
if (newY < 0 || newY > 4) newY = y;
if (board[newX][newY] == *in)
match = matchword(in+1, newX, newY);
}
}
return match;
}
bool matchword(char* in)
{
bool match = false;
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
if (board[i][j] == *in)
match = matchword(in+1, i, j);
}
}
return match;
}
void main (int argc, char** argv)
{
char* array[]={ "STAR", "TONE", "NOTE", "SAND" };
for (int i = 0; i < 4; i++)
{
char* res;
if (matchword(array[i]))
res = "YES";
else
res = "NO";
cout<<array[i]<<"-"<<res<<endl;
}
_getch();
}
I think we can use BST to solve this problem by having another one variable to keep the count of each character.
Since the word contains only four characters.so we can use four variables to keep track of the count while searching for given word..
For eg:
when we search for the word STARS
let us assume BST contains count for S-1,T-3,A-2,R-1.
first we will check S in BST and store the count in a variable by decrementing one.now the count will become zero.when we search for S at the end of the string ,before that we search the count variable..Now count for char S will be 0..So the given word doest exist..
Its enough to form a BST with 26 different letters[a-z] at the maximum..if each char occurs at any no of time we can have count variable..
I found another one solution to this problem.The idea is take each character from 4*4 matrix and compare it with the all character of the given word to search.
if matches then replace that char in the given word to 0 0r some other special char.
and also have a count variable which incremented by one for each char matches..
If the count be 4 and all the char in the given word is replaced by 0.
then given word found in the matrix.
Here's a recursive solution in Java :
public class Board {
static char [] word;
static char [][] board;
public static boolean inBoard(char [][] inBoard, String inWord){
board = inBoard;
word = inWord.toCharArray();
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(inBoardAux(i,j,0))
return true;
return false;
}
public static boolean inBoardAux(int i, int j, int start){
if(board[i][j]!=word[start])
return false;
else if(start==word.length-1)
return true;
for(int k=i-1;k<=i+1;k++)
for(int l=j-1;l<=j+1;l++)
if((k!=i || l!=j) && 0<=k && k<4 && 0<=l && l<4 ){
if(inBoardAux(k,l,start+1))
return true;
}
return false;
}
public static void main(String [] args){
char [][] tBoard = {{'s','m','e','f'},{'r','a','t','d'},{'l','o','n','i'},{'s','m','e','f'}};
System.out.println(inBoard(tBoard, "sand"));
}
}
/**
* Given an virtual 4x4 boggle board, and some 4 letter words, determine if the words are in the board
* ex.
*
* S M E F
* R A T D
* L O N I
* K A F B
*
* STAR- no
* TONE- no
* NOTE- yes
* SAND- yes
* etc.
* @author patrick
*
*/
public class Board {
public static void main(String[] args) {
char[][] board = new char[][]{
{'S','M','E','F'},
{'R','A','T','D'},
{'L','O','N','I'},
{'K','A','F','B'}
};
String[] words = new String[] {"STAR", "TONE", "NOTE", "SAND"};
for(String word : words) {
char[] letters = word.toCharArray();
Coordinate[] starters = find(board, letters[0]);
boolean found = false;
for(Coordinate starter : starters) {
if(boggleHelper(board, letters, 1, starter, null)) {
System.out.println(word + " - YES");
found = true;
break;
}
}
if(!found) {
System.out.println(word + " - NO");
}
}
}
private static boolean boggleHelper(char[][] board, char[] word, int index, Coordinate current, Coordinate origin) {
if(index >= word.length) {
return true;
}
Coordinate[] neighbors = findNeighbors(board, current, origin);
for(Coordinate neighbor : neighbors) {
if(board[neighbor.y][neighbor.x] == word[index]) {
if(boggleHelper(board, word, index+1, neighbor, current)) {
return true;
}
}
}
return false;
}
public static Coordinate[] findNeighbors(char[][] board, Coordinate current, Coordinate origin) {
Coordinate[] all = new Coordinate[] {
new Coordinate(current.y+1, current.x-1),
new Coordinate(current.y+1, current.x),
new Coordinate(current.y+1, current.x+1),
new Coordinate(current.y, current.x-1),
new Coordinate(current.y, current.x+1),
new Coordinate(current.y-1, current.x-1),
new Coordinate(current.y-1, current.x),
new Coordinate(current.y-1, current.x+1)
};
List<Coordinate> result = new ArrayList<Coordinate>(all.length);
for(Coordinate c : all) {
if(c.y >=0 && c.y<4 && c.x>=0 && c.x<4 && !c.equals(origin)) {
result.add(c);
}
}
return result.toArray(new Coordinate[result.size()]);
}
private static Coordinate[] find(char[][] board, char c) {
List<Coordinate> results = new LinkedList<Coordinate>();
for(int y=0; y<4; y++) {
for(int x=0; x<4;x++) {
if(board[y][x] == c) {
results.add(new Coordinate(y, x));
}
}
}
return results.toArray(new Coordinate[results.size()]);
}
}
public class Coordinate {
public int x;
public int y;
public Coordinate() {}
public Coordinate(int y, int x) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object obj) {
if(obj instanceof Coordinate) {
Coordinate c = (Coordinate)obj;
return this.x == c.x && this.y == c.y;
}
return false;
}
@Override
public int hashCode() {
return y*10 + x;
}
}
using System;
using System.IO;
using System.Collections.Generic;
class FaceBook
{
public static void Main(){
char[][] board=new char[][]{
new char[]{'S','M','E','F'},
new char[]{'R','A','T','D'},
new char[]{'L','O','N','I'},
new char[]{'K','A','F','B'}
};
BoggleBoard _4x4Board=new BoggleBoard(board);
Console.WriteLine("STAR:{0}", _4x4Board.Match("STAR"));
Console.WriteLine("TONE:{0}", _4x4Board.Match("TONE"));
Console.WriteLine("NOTE:{0}", _4x4Board.Match("NOTE"));
Console.WriteLine("SAND:{0}", _4x4Board.Match("SAND"));
}
public class BoggleBoard
{
public Dictionary<int,char> listBorad=new Dictionary<int,char>();
List<List<int>> foundList=new List<List<int>>();
HashSet<int> setOKLoc =new HashSet<int>();
HashSet<int> foundLoc =new HashSet<int>();
private char[][] board;
public BoggleBoard(char[][] board1)
{
this.board=board1;
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
{
listBorad.Add((i*4)+j+1,board[i][j]);
}
}
public bool Match(string input){
setOKLoc.Clear();
foundList.Clear();
foundLoc.Clear();
for(int i=0;i<input.Length;i++)
{
int loc=0;
if(Find(input[i],out loc))
{
generateNighbure(loc);
if(i!=0 && !IsNighbour(loc))
return false;
}
}
return true;
}
private bool Find(char chr,out int loc){
loc=-1;
foreach(var pair in listBorad)
{
if(pair.Value==chr){
if(foundLoc.Add(pair.Key))
{
loc=pair.Key;
return true;
}
}
}
return false;
}
private void generateNighbure(int loc)
{
int[] nighbours={1,4};
int temp=0;
for(int i=0;i<=1;i++)
{
temp=loc+nighbours[i];
if(temp>0 && temp<=16)
{
setOKLoc.Add(temp);
}
temp=loc-nighbours[i];
if(temp>0 && temp<=16)
{
setOKLoc.Add(temp);
}
}
}
private bool IsInFoundList(int i,int j)
{
foreach(var l in foundList)
{
if (l[0]==i && l[1]==j )
return true;
}
return false;
}
private bool IsNighbour(int newLoc)
{
foreach(var item in setOKLoc){
if(item==newLoc)
return true;
}
return false;
}
}
}
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
using namespace std;
bool check(vector<vector<char> > v,string str){
for(int i=0;i<v.size();i++){
for(int j=0;j<v[i].size();j++){
int index=0;
stack<int> stkx;
stack<int> stky;
stkx.push(i);
stky.push(j);
while(!stkx.empty()){
int x = stkx.top();
int y = stky.top();
stkx.pop();
stky.pop();
// cout<<i<<" "<<j<<endl;
if(v[x][y]==str[index]){
//cout<<v[x][y]<<endl;
index++;
//we got out letter..lets apply dfs here
for(int k=-1;k<2;k++){
for(int l=-1;l<2;l++){
if(k==0 && l==0){}
else{
if(x+k>=0 && x+k<4 && y+l>=0 && y+l<4 && v[x+k][y+l]==str[index]){
stkx.push(x+k);
stky.push(y+l);
}
}
}
}
if(index == str.length())
return true;
}
}
}
}
return false;
}
int main(){
vector<vector<char> > v;
for(int i=0;i<4;i++){
vector<char> temp;
for(int j=0;j<4;j++){
char x;
cin>>x;
temp.push_back(x);
}
v.push_back(temp);
}
int n;
do{
string str;
cin>>str;
if(check(v,str))
cout<<"This word is in board"<<endl;
else
cout<<"This word is not in board"<<endl;
}while(1);
return 0;
}
Ruby implementation:
#!/usr/bin/ruby
#
require 'pp'
# Find a character on the boggle board
#
# ==== Attributes
#
# boggle: the board
# char: The char we want to find
#
# ==== Return
#
# Returns a hash with the position or nil if it is not found
#
# { :x => 0, :y => 0 }
def find_char boggle, char
boggle.each_with_index do |row,row_num|
if (column = row.index(char)) != nil
return {
:y => column,
:x => row_num
}
end
end
return nil
end
# In two chars return true if char_a is neightbor of char_b
#
# ==== Attributes
#
# char_a,char_b: the two chars to evaluate
#
# ==== Return
#
# true,false
#
def are_neighbor? boggle,char_a,char_b
pos_a = find_char boggle,char_a
pos_b = find_char boggle,char_b
if pos_a == nil or pos_b == nil
return false
end
if pos_a[:x].between?(pos_b[:x]-1,pos_b[:x]+1) and pos_a[:y].between?(pos_b[:y]-1,pos_b[:y]+1)
return true
end
return false
end
def validate_word boggle, word
if find_char boggle,char == nil
return false
end
if index != 0
if not are_neighbor? boggle, word[index], word[index-1]
return false
end
end
end
return true
end
boggle = [
['S','M','E','F'],
['R','A','T','D'],
['L','O','N','I'],
['K','A','F','B'],
]
pp validate_word boggle, "STAR"
pp validate_word boggle, "TONE"
pp validate_word boggle, "NOTE"
pp validate_word boggle, "SAND"
C# - iI think is the most efficient way:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication2
{
class FindWordInBoard
{
public static void MainFunc()
{
char[][] newBoard = new char[4][];
newBoard[0]= new char[4]{'S','M','E','F'};
newBoard[1] = new char[4] { 'R', 'A', 'T', 'D' };
newBoard[2] = new char[4] { 'L', 'O', 'N', 'I' };
newBoard[3] = new char[4] { 'K', 'A', 'F', 'B' };
Console.WriteLine(findWordOnBoard(newBoard, "STAR"));
Console.WriteLine(findWordOnBoard(newBoard, "TONE"));
Console.WriteLine(findWordOnBoard(newBoard, "NOTE"));
Console.WriteLine(findWordOnBoard(newBoard, "SAND"));
Console.Read();
}
static bool findWordOnBoard(char[][] inBoard, string word)
{
int n = 4;
int m = 4;
var board=AddEdges(inBoard, n + 1, m + 1);
char currChar = word[0];
for (int i = 1; i < n + 1; i++)
{
for (int j = 1; j < m + 1; j++)
{
if (currChar == board[i][j])
{
bool isFound = FindPathOnBoard(board, word.Substring(1), i, j);
if (isFound)
{
return true;
}
}
}
}
return false;
}
static bool FindPathOnBoard(char[][] board, string currWord, int start_i, int start_j)
{
if (currWord.Length == 0)
{
return true;
}
char currChar = currWord[0];
for (int i = -1; i < 2; i++)
{
for (int j = -1; j < 2; j++)
{
if (board[start_i + i][start_j + j] == currChar)
{
bool isFound = FindPathOnBoard(board, currWord.Substring(1), start_i + i, start_j + j);
if (isFound)
{
return true;
}
}
}
}
return false;
}
static char[][] AddEdges(char[][] board, int n, int m)
{
char[][] newBoard = new char[n + 1][];
for (int i = 0; i < n+1; ++i)
newBoard[i] = new char[m+1];
for (int i = 0; i < n + 1; i++)
{
for (int j = 0; j < m + 1; j++)
{
if (j < 1 || j > m - 1 || i < 1 || i > n - 1)
{
newBoard[i][j] = '1';
}
else
{
newBoard[i][j] = board[i - 1][j - 1];
}
}
}
return newBoard;
}
}
}
public static boolean scan(String wordToCheck) {
boolean flag = true;
int count = 0;
for (char character: wordToCheck.toCharArray()) {
for (int j=0; j<4; j++) {
for (int k=0; k<4; k++) {
if (array[j][k] == character) {
count++;
if (count == wordToCheck.length()) {return true;}
}
}
}
}
return false;
}
DFS-like solution, in which you erase the wrong path when going back the recursive calls.
public class BoggleBoard {
public static boolean hasWord(String word, char[][] board) {
int n = board.length;
boolean[][] currentPath = new boolean[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (findWord(word, 0, board, i, j, currentPath)) {
return true;
}
}
}
return false;
}
// If find, returns true and the path altered. Else return false, and path unaltered
// Handles empty string cases
private static boolean findWord(String word, int init, char[][] board, int i, int j, boolean[][] currentPath) {
if (init == word.length()-1)
return (board[i][j] == word.charAt(init));
if (init >= word.length() || board[i][j] != word.charAt(init))
return false;
currentPath[i][j] = true;
for (int x = i - 1; x <= i + 1; x++) {
for (int y = j - 1; y <= j + 1; y++) {
if (x >= 0 && x < board.length &&
y >= 0 && y < board.length &&
!currentPath[x][y] &&
findWord(word, init + 1, board, x, y, currentPath)) {
return true;
}
}
}
currentPath[i][j] = false;
return false;
}
public static void main(String[] args) {
char[][] board = {{'s','m','e','f'},{'r','a','t','d'},{'l','o','n','i'},{'k','a','f','b'}};
System.out.println(hasWord("star", board));
System.out.println(hasWord("tone", board));
System.out.println(hasWord("note", board));
System.out.println(hasWord("sand", board));
System.out.println(hasWord("", board));
}
}
public class Main
{
public static void main(String[] args)
{
char [][] board = {{'S','M','E','F'}, {'R', 'A', 'T', 'D'}, {'L', 'O', 'N', 'I'}, {'K', 'A', 'F', 'B'}};
System.out.println(boardContainsWord(board, "STAR"));
System.out.println(boardContainsWord(board, "TONE"));
System.out.println(boardContainsWord(board, "NOTE"));
System.out.println(boardContainsWord(board, "SAND"));
}
public static boolean boardContainsWord(char [][] board, String word)
{
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for(int i = 0; i < board.length; i++)
{
for(int j = 0; j < board[0].length; j++)
{
map.put(board[i][j], i * board.length + j);
}
}
for(int i = 0; i < word.length() - 1; i++)
{
Integer index = map.get(word.charAt(i));
if(index == null || !getNeighbors(board, index).contains(word.charAt(i + 1)))
{
return false;
}
}
return true;
}
public static HashSet<Character> getNeighbors(char [][] board, int index)
{
final int size = board.length;
final int row = index / size;
final int col = index % size;
HashSet<Character> set = new HashSet<Character>();
for(int i = row - 1; i <= row + 1; i++)
{
for(int j = col - 1; j <= col + 1; j++)
{
if((i == row && j == col) || i < 0 || j < 0 || i > size - 1 || j > size - 1)
{
continue;
}
set.add(board[i][j]);
}
}
return set;
}
}
I implemented this as a graph problem following a BFS scheme but not entirely BFS, here is my code in Java -
import java.io.File;
import java.util.HashMap;
import java.io.FileReader;
import java.util.ArrayList;
import java.io.IOException;
import java.io.BufferedReader;
/* this class is used to form a graph out of the input boggle matrix characters */
class BoggleGraph{
// the number of vertices in the graph
int nVertices;
// this boolean variable holds the kind of graph one wants, directed or undirected */
boolean isDirected;
// this hashmap holds the adjacency list of the graph data structure
HashMap<Character, ArrayList<Character>> adjacencyList;
// this is the constructor for the class, which constructs a graph object
public BoggleGraph(int nVertices, boolean isDirected){
this.nVertices = nVertices;
this.isDirected = isDirected;
this.adjacencyList = new HashMap<Character, ArrayList<Character>>();
}
// these functions help retrieve the fields of the graph data structure
public int getVertices(){
return this.nVertices;
}
public boolean getIsDirected(){
return this.isDirected;
}
public HashMap<Character, ArrayList<Character>> getAdjacencyList(){
return this.adjacencyList;
}
// this function helps insert an edge in a graph
public void insertEdge(char vertex1, char vertex2, boolean isDirected){
if(isDirected){
if(adjacencyList.containsKey(vertex1)){
if(!adjacencyList.get(vertex1).contains(vertex2))
adjacencyList.get(vertex1).add(vertex2);
}
else{
adjacencyList.put(vertex1, new ArrayList<Character>());
adjacencyList.get(vertex1).add(vertex2);
}
}else{
if(adjacencyList.containsKey(vertex1))
adjacencyList.get(vertex1).add(vertex2);
else{
adjacencyList.put(vertex1, new ArrayList<Character>());
adjacencyList.get(vertex1).add(vertex2);
}
insertEdge(vertex2, vertex1, true);
}
}
// this function is used to display the graph
public void displayGraph(){
for(Character vertex : adjacencyList.keySet()){
System.out.print(vertex + " : ");
for(Character adj : adjacencyList.get(vertex))
System.out.print(adj + " ");
System.out.println();
}
}
}
public class Problem1_BoggleGameQuestion {
// this function checks if a word can be formed out of the input Boggle Matrix
public static boolean checkWord(BoggleGraph bgraph, String word){
HashMap<Character, Boolean> visitedMap = new HashMap<Character, Boolean>();
for(Character c : bgraph.getAdjacencyList().keySet())
visitedMap.put(c, false);
visitedMap.put(word.charAt(0), true);
ArrayList<Character> frontier = bgraph.getAdjacencyList().get(word.charAt(0));
for(int i = 1; i < word.length(); ++i){
if(frontier.contains(word.charAt(i)) && !visitedMap.get(word.charAt(i))){
visitedMap.put(word.charAt(i), true);
frontier = bgraph.getAdjacencyList().get(word.charAt(i));
}else{
return false;
}
}
return true;
}
public static void main(String[] args) throws NumberFormatException, IOException{
BufferedReader br = new BufferedReader(new FileReader(new File("C:/Users/ankitsablok89/Desktop/MS in Computer Science Classes/Competitive Programming/Interview Problems/BoggleGame.txt")));
int dimensions = Integer.parseInt(br.readLine());
char[][] boggleBoard = new char[dimensions][dimensions];
for(int i = 0; i < dimensions; ++i){
for(int j = 0; j < dimensions; ++j){
boggleBoard[i][j] = br.readLine().charAt(0);
}
}
BoggleGraph bgraph = new BoggleGraph(dimensions*dimensions, true);
for(int i = 0; i < dimensions; ++i){
for(int j = 0; j < dimensions; ++j){
if(i-1 >= 0)
bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i-1][j], bgraph.isDirected);
if(i+1 < dimensions)
bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i+1][j], bgraph.isDirected);
if(j-1 >= 0)
bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i][j-1], bgraph.isDirected);
if(j+1 < dimensions)
bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i][j+1], bgraph.isDirected);
if(i-1 >= 0 && j-1 >= 0)
bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i-1][j-1], bgraph.isDirected);
if(i+1 < dimensions && j-1 >= 0)
bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i+1][j-1], bgraph.isDirected);
if(i-1 >= 0 && j+1 < dimensions)
bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i-1][j+1], bgraph.isDirected);
if(i+1 < dimensions && j+1 < dimensions)
bgraph.insertEdge(boggleBoard[i][j], boggleBoard[i+1][j+1], bgraph.isDirected);
}
}
System.out.println(checkWord(bgraph, "STAR"));
System.out.println(checkWord(bgraph, "TONE"));
System.out.println(checkWord(bgraph, "NOTE"));
System.out.println(checkWord(bgraph, "SAND"));
}
}
I think the other solutions do not handle usage of the same character twice. Below is the bug free solution.
- Melih March 30, 2013