CareerCup

Sample program with code

Please correct me if u found any thing wrong or any issues in the code.

/**
 * Load the dictionary into trie
 * Process the array in all directions and add the word to a list
 *     ^   ^  ^
 *      \  | /
 *   <--   a   -->
 *      /  |  \
 *     v   v   v
 *
 *     process --> Method will take row and coulmn 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 Trie trie;

    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 trie = testMatrixExample.new Trie();
        testMatrixExample.setTrie(trie);
        String[] strs =
        { "mad", "Aunt", "dad", "do", "pot", "top", "dot", "Meet", "to", "end", "mud", "eno", "dam", "me", "dum" };
        for (String str : strs) {
            trie.insert(str);
        }
        System.out.println(trie.search("prakash"));
        //trie.print();
        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();
        Trie trie = this.getTrie();
        LinkedHashSet<String> al = new LinkedHashSet<String>();
        if (trie == 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 = trie.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 = trie.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 = trie.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 = 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, j = col; i < chars.length && j >= 0; i++, j--) {
            builder.append(chars[i][j]);
            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, j = col; i >= 0 && j < chars.length; i--, j++) {
            builder.append(chars[i][j]);
            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, j = col; i >= 0 && j >= 0; i--, j--) {
            builder.append(chars[i][j]);
            search = trie.search(builder.toString());
            if (search == 0) {
                al.add(builder.toString());
            } else if (search == 2 || search == -1)
                break;
        }
        return al;
    }

    public void setTrie(Trie trie) {
        this.trie = trie;
    }

    public Trie getTrie() {
        return trie;
    }


    class Trie {
        private TrieNode root;

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

        public int search(String pattern) {
            TrieNode root = this.getRoot();
            if (root == null)
                return -1;
            int i = 0;
            for (i = 0; i < pattern.length(); i++) {
                root = root.getTrieArray()[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() {
            TrieNode root = this.getRoot();
            if (root == null) {
                return;
            }
            char[] buffer = new char[1024];
            traverse(buffer, 0, root);
        }

        public void traverse(char[] buffer, int index, TrieNode 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.getTrieArray()[i] != null) {
                    buffer[index] = root.getTrieArray()[i].getData();
                }
                traverse(buffer, index + 1, root.getTrieArray()[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(TrieNode root) {
            this.root = root;
        }

        public TrieNode getRoot() {
            return root;
        }
    }


    class TrieNode {
        private boolean word;
        private char data;
        private int noc;
        private TrieNode[] trieArray;


        public TrieNode(char data) {
            this.setData(data);
            this.setTrieArray(new TrieNode[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 setTrieArray(TrieNode[] trieArray) {
            this.trieArray = trieArray;
        }

        public TrieNode[] getTrieArray() {
            return trieArray;
        }
    }
}

It is working only for 2 by 2 or 3 by 3 matrix not for 4 by 5 and so on.

v