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

Question

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.

Answer 1

/** 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);
    LinkedHashSet<String> list = new LinkedHashSet<String>();
    for (int i = 0; i < charArray.length; i++) {
        for (int j = 0; j < charArray[i].length; j++) {
            list.addAll(testMatrixExample.process(i, 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();
    LinkedHashSet<String> al = new LinkedHashSet<String>();
    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) {
            al.add(builder.toString());
        } 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) {
            al.add(builder.toString());
        } 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) {
            al.add(builder.toString());
        } 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) {
            al.add(builder.toString());
        } 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) {
            al.add(builder.toString());
        } 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) {
            al.add(builder.toString());
        } 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) {
            al.add(builder.toString());
        } 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) {
            al.add(builder.toString());
        } 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;
    }
}