# Find non-distinct occurrences of the words found in the array?

+1 vote
587 views

Given a 2d matrix with characters and a dictionary. Find non-distinct occurrences of the words found in the array, horizontally, vertically or diagonally, and also the reverse in each direction.

posted Sep 16, 2013

+1 vote

/** Load the dictionary into tree, Process the array in all directions and add the word to a list, Method will take row and column numbers as input and it will return the all the unique dictionary words in all directions */

``````import java.util.LinkedHashSet;
public class TestMatrixExample {
private char[][] charArray;
private Tree tree;
public TestMatrixExample() {
super();
}

public TestMatrixExample(int n) {
this.setCharArray(new char[n][n]);
}

public static void main(String[] args) {
TestMatrixExample testMatrixExample = new TestMatrixExample();
TestMatrixExample.Trie tree = testMatrixExample.new Tree();
testMatrixExample.setTree(tree);
String[] strs =
{ "mad", "Aunt", "dad", "do", "pot", "top", "dot", "Meet", "to", "end", "mud", "eno", "dam", "me", "dum" };
for (String str : strs) {
tree.insert(str);
}
System.out.println(tree.search("prakash"));

char[][] charArray =
{ { 'm', 'a', 'd', 'd' }, { 'e', 'u', 'a', 'o' }, { 'e', 'n', 'd', 't' }, { 't', 't', 'o', 'p' } };
testMatrixExample.setCharArray(charArray);
for (int i = 0; i < charArray.length; i++) {
for (int j = 0; j < charArray[i].length; j++) {
}
}
System.out.println(list);
}

public void setCharArray(char[][] charArray) {
this.charArray = charArray;
}

public char[][] getCharArray() {
return charArray;
}

public LinkedHashSet<String> process(int row, int col) {
StringBuilder builder = new StringBuilder();
char[][] chars = this.getCharArray();
Tree tree = this.getTree();
if (tree == null)
return null;
int search = 0;
//Column wise  Processing
for (int i = row; i < chars.length; i++) {
builder.append(chars[i][col]);
search = trie.search(builder.toString());
if (search == 0) {
} else if (search == 2 || search == -1)
break;
}
builder = new StringBuilder();
for (int i = row; i >= 0; i--) {
builder.append(chars[i][col]);
search = tree.search(builder.toString());
if (search == 0) {
} else if (search == 2 || search == -1)
break;
}

//Row wise Processing
builder = new StringBuilder();
for (int i = col; i < chars[row].length; i++) {
builder.append(chars[row][i]);
search = tree.search(builder.toString());
if (search == 0) {
} else if (search == 2 || search == -1)
break;
}
builder = new StringBuilder();
for (int i = col; i >= 0; i--) {
builder.append(chars[row][i]);
search = tree.search(builder.toString());
if (search == 0) {
} else if (search == 2 || search == -1)
break;
}

//Diagonal Processing(Upper and Lower)
builder = new StringBuilder();
for (int i = row, j = col; i < chars.length && j < chars[i].length; i++, j++) {
builder.append(chars[i][j]);
search = tree.search(builder.toString());
if (search == 0) {
} else if (search == 2 || search == -1)
break;
}
builder = new StringBuilder();
for (int i = row, j = col; i < chars.length && j >= 0; i++, j--) {
builder.append(chars[i][j]);
search = tree.search(builder.toString());
if (search == 0) {
} else if (search == 2 || search == -1)
break;
}
builder = new StringBuilder();
for (int i = row, j = col; i >= 0 && j < chars.length; i--, j++) {
builder.append(chars[i][j]);
search = tree.search(builder.toString());
if (search == 0) {
} else if (search == 2 || search == -1)
break;
}
builder = new StringBuilder();
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
builder.append(chars[i][j]);
search = tree.search(builder.toString());
if (search == 0) {
} else if (search == 2 || search == -1)
break;
}
return al;
}

public void setTree(Tree tree) {
this.tree = tree;
}

public Tree getTree() {
return tree;
}

class Tree {
private TreeNode root;

public void insert(String pat) {
TreeNode root = this.getRoot();
if (root == null) {
root = new TreeNode(' ');
this.setRoot(root);
}
int k = 0;
for (int i = 0; i < pat.length(); i++) {
k = atoi(pat.charAt(i));
if (root.getTreeArray()[k] == null) {
root.getTreeArray()[k] = new TreeNode(pat.charAt(i));
}
root = root.getTreeArray()[k];
}
root.setWord(true);
}

public int search(String pattern) {
TreeNode root = this.getRoot();
if (root == null)
return -1;
int i = 0;
for (i = 0; i < pattern.length(); i++) {
root = root.getTreeArray()[atoi(pattern.charAt(i))];
if (root == null) {
break;
}
}
if (root != null && root.isWord())
return 0;
if (i > 0)
return 1;
return 2;
}

public void print() {
TreeNode root = this.getRoot();
if (root == null) {
return;
}
char[] buffer = new char[1024];
traverse(buffer, 0, root);
}

public void traverse(char[] buffer, int index, TreeNode root) {
if (root == null)
return;
if (root.isWord()) {
System.out.println(new String(buffer, 0, index));
}
for (int i = 0; i < 26; i++) {
if (root.getTreeArray()[i] != null) {
buffer[index] = root.getTreeArray()[i].getData();
}
traverse(buffer, index + 1, root.getTreeArray()[i]);
}
}

public int atoi(char ch) {
int i = -1;
if (ch >= 65 && ch <= 90) {
return ch - 65;
}
if (ch >= 97 && ch <= 122) {
return ch - 97;
}
return i;
}
public void setRoot(TreeNode root) {
this.root = root;
}
public TreeNode getRoot() {
return root;
}
}

class TreeNode {
private boolean word;
private char data;
private int noc;
private TreeNode[] treeArray;

public TreeNode(char data) {
this.setData(data);
this.setTreeArray(new TreeNode[26]);
}

public void setWord(boolean word) {
this.word = word;
}

public boolean isWord() {
return word;
}

public void setData(char data) {
this.data = data;
}

public char getData() {
return data;
}

public void setNoc(int noc) {
this.noc = noc;
}

public int getNoc() {
return noc;
}

public void setTreeArray(TreeNode[] treeArray) {
this.treeArray = treeArray;
}

public TreeNode[] getTreeArray() {
return treeArray;
}
}
``````
Similar Questions

Question: C#, Java or VB.Net

Given the following:

``````public static class PuzzleSolver
{
public static string[] DICTIONARY = {"OX","CAT","TOY","AT","DOG","CATAPULT","T"};
static bool IsWord(string testWord)
{
if (DICTIONARY.Contains(testWord))

return true;

return false;
}
}
``````

Now Implement the function public static int FindWords(char[,] puzzle), FindWords should return the number of all non-distinct occurrences of the words found in the array, horizontally, vertically or diagonally, and also the reverse in each direction.

Example Input 1:

``````CAT
XZT
YOT
``````

Example Output 1:

``````8
(AT, AT, CAT, OX, TOY, T, T, T)
``````

Example Input 2:

``````CATAPULT
XZTTOYOO
YOTOXTXX
``````

Example Output 2:

``````22
``````

Given a string and two words which are present in the string, find the minimum distance between the words

Example:
"the brown quick frog quick the", "the" "quick"
Min Distance: 1

"the quick the brown quick brown the frog", "the" "brown"
Min Distance: 2