top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

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

+1 vote
734 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 by Vinay Shukla

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

+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);
    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;
    }
}
answer Sep 17, 2013 by Arvind Singh
Similar Questions
+2 votes

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
+2 votes

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

C/Java code would be helpful?

0 votes

Suppose you are given "Luv you 123 luv me" the expected output is "vuL uoy 123 vul em"

...