0

My objective is to find all words 2 to 5 letters in length from a 5x5 matrix. my search method works but it does not work for every word in the dictionary.

Search method:

public static void Search(char board[][])
{
    int X = board.length;
    int Y = board[0].length;
    //Mark all characters as not visited
    boolean visited[][] = new boolean[X][Y];
    //Initialize current string
    String str = "";
    //Consider every character and look for all words
    //starting with this character
    for(int i=0;i<X;i++)
    {
        for(int j=0;j<Y;j++)
        {
            System.out.println("Starting at: "+i+" "+j);
            WordsFound(board, visited, i, j, str);
        }
    }
}

WordsFound method:

public static void WordsFound(char board[][], boolean visited[][], int i, int j, String str)
{
    visited[i][j] = true;
    if(str.length() == 5)
        return;
    str = str + board[i][j];
    //If the word is present in dictionary, then print it
    if(isWord(str))
        System.out.println("Found Word: "+str);
    int X = board.length;
    int Y = board[0].length;
    //Search the word in the 5 by 5 matrix.
    for(int row=i-1;row<=i+1 && row<X;row++)
    {
        for(int col=j-1;col<=j+1 && col<Y;col++)
        {
            if(row>=0 && col>=0 && !visited[row][col])
                //Call the method WordsFound.
                WordsFound(board,visited, row, col, str);
        }
    }
    if(str != null && str.length() > 0 ) 
    {
        str = str.substring(0, str.length()-1);
    }
    visited[i][j] = false;
}

main class:

public static void main(String[] args) throws FileNotFoundException
{
    readFile("dictionary.txt");
    char board[][] = {
            {'R','A','H','J','M'},
            {'Y','U','W','W','K'},
            {'R','X','N','F','M'},
            {'Q','G','E','E','B'},
            {'E','O','A','P','E'}};
    System.out.println("R A H J M\nY U W W K\nR X N F M\nQ G E E B\nE O A P E");
    System.out.println("");
    Search(board);
}

My program does find the word "RAW" but why doesn't it find the word "RUN"?

Running the program just showing the index 0 0:

R A H J M
Y U W W K
R X N F M
Q G E E B
E O A P E

Starting at: 0 0
Found Word: RAY
Found Word: RAW
Corey B.
  • 11
  • 1
  • 6
  • Your result looks quite strange - where in your matrix are `RAY` and `RAW` (assuming you should consider only vertical, horizontal and diagonal words) ? Or is the matrix layout completely irrelevant, and you should find all words that can be built from the 25 letters (regardless of the matrix layout) ? – Frank Schmitt Nov 16 '17 at 17:17
  • the words are all in a txt file, there are about 26,000 words in that file. I didn't show the file I/O becuase I didn't think that was the problem; and yes I'm assuming vertical horizontal and diagonal words. it only finds 2 words but there are others that it's not catching such as `RUNG` and `RUNE`. – Corey B. Nov 16 '17 at 17:23
  • Also, you seem to be treating strings as mutable so I don't think it's doing what you think it's doing. See https://stackoverflow.com/a/17942294/229743 – Taylor Nov 16 '17 at 17:23
  • 1
    What are the rules for finding a word? Do the letters all need to be in a line? I'd take the inverse approach, of going through the words and searching the grid for them. – Taylor Nov 16 '17 at 17:28
  • @FrankSchmitt The matrix layout is irrelevant, I need to find all possible words that are in the dictionary in any 5x5 matrix. – Corey B. Nov 16 '17 at 17:29
  • @CoreyB. You misunderstood me - you do not only find *too few* words, you also find *words that are not there*, so you've got a mixture of false positives and false negatives. – Frank Schmitt Nov 16 '17 at 17:30
  • @Taylor the words can be in any direction, I need to find words 2 to 5 letters long but say we start at index 0 2, and the length of the word doesn't matter, an acceptable word would be `HUNGRY`. – Corey B. Nov 16 '17 at 17:32
  • @FrankSchmitt, for RAY, go east then south-west, for RAW, go east then south-east. – Shihab Shahriar Khan Nov 16 '17 at 17:33
  • Again, go through the words and search the grid for each word. – Taylor Nov 16 '17 at 17:34
  • Thank you all, I will work on this and get back with progress – Corey B. Nov 16 '17 at 17:39

1 Answers1

0

To find "RUN", you need to ensure when you are in "U", "N" is not already visited, otherwise you won't go to that cell.

But since you are running dfs, the "N" cell might already be visited from a cell around it other than "U", which will set visited for "N" true, and search from "U" will fail.

To solve it, you will need to have 3D visited, where apart from indexes, you will also need to store path traversed so far. (i.e the string so far)

EDIT: I'm from python. So I wasn't aware of the complexity of mixing int and string as I suggested for visited variable. Just use hash of the string instead of the direct string, it will also be a lot space-efficient.

Shihab Shahriar Khan
  • 4,930
  • 1
  • 18
  • 26