CODEWITHSUNDEEP
javaarrayscharcombinations
user1929899
user1929899

Reputation:

All possible combinations of strings from char array in Java

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!

Upvotes: 0

Views: 2149

Answers (3)

Azerogg
Azerogg

Reputation: 93

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.

Upvotes: 0

meriton
meriton

Reputation: 70564

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.

Upvotes: 2

David Duncan
David Duncan

Reputation: 1215

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.

Upvotes: 0

Related Questions