0

I'm having a school project for Java and I'm assigned too. Now I'm having an issue with a part of the project which I can't figure out. The application must generate all possible word combinations (can be verified via a dictionary) from a two-dimensional char array (char[][] board). The board is dynamic as the user can choose the scale: 4x4, 5x5, 4x5, 5x4, 4x6, ... So I guess a nested loop wouldn't be approriate here, correct me if I'm wrong. Words must be generated horizontally, verticaly and diagonally. Example of a 4x4 board:

| u | a | u | s |

| n | n | i | i |

| a | o | e | b |

| e | u | e | z |

    Code was completely wrong.

Another idea may be to brute force every possible path on the board and then try those saved paths to verify whether it's a word or not.

Thanks in advance!

Improve this question
4
  • What do you mean with "generate words on the board"? What is your input, and what it the desired output? Commented Jan 20, 2013 at 19:19
  • The application generates a board on a random base (with random chars) and must then find all possible words on the board in multiple directions (horizontally, vertically and diagonally) and may not visit a character twice. Commented Jan 20, 2013 at 19:57
  • What does "in multiple directions" mean? Can a single word use multiple directions, i.e. does the word have to be in a straight line or may it curve across the board? Commented Jan 20, 2013 at 20:15
  • All possible directions, once the cursor (let's say) selects a character from there on, it can go jump to all its neighboors and so on ... The actual directions it can go to are saved in the HashMap<Point, Point[]> neighbouringCoords; Commented Jan 20, 2013 at 20:38

3 Answers 3

Reset to default
2

One way to solve this is:

for each path on the board
    if corresponding word in dictionary
        print it

To find all paths, you could adapt any graph traversal algorithm.

Now this will be really slow, because there are a great many paths of a board that size (for a board with n cells, we can have at most n * 4 ^ (n - 1) paths, so for a 5 by 5 board, you'd have something like 25 * 2 ^ 50 ~= 10^16 paths.

One way to improve on this is to interleave traversing the graph and checking the dictionary, aborting if the current path's word is not a prefix of a dictionary word:

class Board {

    char[][] ch;
    boolean[][] visited;

    Trie dictionary;

    void find() {
        StringBuilder prefix = new StringBuilder();
        for (int x = 0; x < maxx; x++) {
            for (int y = 0; y < maxy; y++) {
                walk(x, y, prefix);
            }
        }
     }

    void walk(int x, int y, StringBuilder prefix) {
        if (!visited[x][y]) {
            visited[x][y] = true;
            prefix.append(ch[x][y]);

            if (dictionary.hasPrefix(prefix)) {
                if (dictionary.contains(prefix)) {
                    System.out.println(prefix);
                }

                int firstX = Math.max(0, x - 1);
                int lastX = Math.min(maxx, x + 1);
                int firstY = Math.max(0, y - 1);
                int lastY = Math.min(maxy, y + 1);
                for (int ax = firstX; ax <= lastX; ax++) {
                    for (int ay = firstY; ay <= lastY; ay++) {
                        walk(ax, ay, prefix);
                    }
                }
            }

            prefix.setLength(prefix.length() - 1);
            visited[x][y] = false;
        }
    }

As you can see, the method walk invokes itself. This technique is known as recursion.

That leaves the matter of finding a data structure for the dictionary that supports efficient prefix queries. The best such data structure is a Trie. Alas, the JDK does not contain an implementation, but fortunately, writing one isn't hard.

Note: The code in this answer has not been tested.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

I now have a somewhat similiar recursive method: private void findWord(Woord woord, int positionInWord, Point currentPosition, HashSet<Point> visited, StringBuilder currentWoord) { ... } and it works, but gives some unusual result at times, like characters which are not connected etc ...
0

A fairly straightforward way of conceptualizing this is to apply a breadth-first search (BFS) approach to each position (or depth-first, depending upon which tweaks you might later want to make). This would give you all possible letter combinations, up to a level of characters equal to the max depth of the search. Depending on your requirements, such as the longest allowed word, max running time, and if a dictionary is provided via a data structure or file, this may be the key part.

Or, you may need to optimize quite a bit more. If so, consider how you might expedite either a BFS or DFS. What if you did a DFS, but knew three characters in that no word starts with "zzz"? You could shave a lot of time off by not having to traverse all conceivable orderings. To look words up effectively, you might need to make further adjustments. But I'd start with Java's built-in functionality (String.startsWith() comes to mind in this instance), measure performance (perhaps with a limited max word length), and then optimize when and where it's needed.

Improve this answer

Comments

0

Start by turning rows , columns and diagonals to Strings, using a simple repetitive method. Then , I would turn it into a StringBuilder or in order to check which words are real and eliminate those which aren't directly from the StringBuilder. then , just print it to a String.There are a lot of useful tools to eliminate or replace words in java.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.