最近我一直在iPhone上玩一款名为《Scramble》的游戏。有些人可能知道这个游戏叫拼字游戏。从本质上讲，当游戏开始时，你会得到一个字母矩阵:
F X I E
A M L O
E W B X
A S T U
The goal of the game is to find as many words as you can that can be formed by chaining letters together. You can start with any letter, and all the letters that surround it are fair game, and then once you move on to the next letter, all the letters that surround that letter are fair game, except for any previously used letters. So in the grid above, for example, I could come up with the words LOB, TUX, SEA, FAME, etc. Words must be at least 3 characters, and no more than NxN characters, which would be 16 in this game but can vary in some implementations. While this game is fun and addictive, I am apparently not very good at it and I wanted to cheat a little bit by making a program that would give me the best possible words (the longer the word the more points you get).
(来源:boggled.org)
不幸的是，我不太擅长算法或它们的效率等等。我的第一次尝试使用一个像这样的字典(约2.3MB)，并进行线性搜索，试图匹配字典条目的组合。这需要花费很长时间来找到可能的单词，因为你每轮只有2分钟的时间，这是不够的。
我很有兴趣看看是否有任何Stackoverflowers可以提出更有效的解决方案。我主要是在寻找使用三大p的解决方案:Python、PHP和Perl，尽管任何使用Java或c++的东西也很酷，因为速度是至关重要的。
目前的解决方案:
Adam Rosenfield, Python， ~20岁
John Fouhy, Python， ~3秒
Kent Fredric, Perl， ~1s
Darius Bacon, Python， ~1s
rvarcher, VB。净,~ 1 s
Paolo Bergantino, PHP(实时链接)，~5s(本地~2s)
import java.util.HashSet;
import java.util.Set;
/**
* @author Sujeet Kumar (mrsujeet@gmail.com) It prints out all strings that can
* be formed by moving left, right, up, down, or diagonally and exist in
* a given dictionary , without repeating any cell. Assumes words are
* comprised of lower case letters. Currently prints words as many times
* as they appear, not just once. *
*/
public class BoggleGame
{
/* A sample 4X4 board/2D matrix */
private static char[][] board = { { 's', 'a', 's', 'g' },
{ 'a', 'u', 't', 'h' },
{ 'r', 't', 'j', 'e' },
{ 'k', 'a', 'h', 'e' }
};
/* A sample dictionary which contains unique collection of words */
private static Set<String> dictionary = new HashSet<String>();
private static boolean[][] visited = new boolean[board.length][board[0].length];
public static void main(String[] arg) {
dictionary.add("sujeet");
dictionary.add("sarthak");
findWords();
}
// show all words, starting from each possible starting place
private static void findWords() {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
StringBuffer buffer = new StringBuffer();
dfs(i, j, buffer);
}
}
}
// run depth first search starting at cell (i, j)
private static void dfs(int i, int j, StringBuffer buffer) {
/*
* base case: just return in recursive call when index goes out of the
* size of matrix dimension
*/
if (i < 0 || j < 0 || i > board.length - 1 || j > board[i].length - 1) {
return;
}
/*
* base case: to return in recursive call when given cell is already
* visited in a given string of word
*/
if (visited[i][j] == true) { // can't visit a cell more than once
return;
}
// not to allow a cell to reuse
visited[i][j] = true;
// combining cell character with other visited cells characters to form
// word a potential word which may exist in dictionary
buffer.append(board[i][j]);
// found a word in dictionary. Print it.
if (dictionary.contains(buffer.toString())) {
System.out.println(buffer);
}
/*
* consider all neighbors.For a given cell considering all adjacent
* cells in horizontal, vertical and diagonal direction
*/
for (int k = i - 1; k <= i + 1; k++) {
for (int l = j - 1; l <= j + 1; l++) {
dfs(k, l, buffer);
}
}
buffer.deleteCharAt(buffer.length() - 1);
visited[i][j] = false;
}
}
下面是使用NLTK工具包中的预定义单词的解决方案
NLTK有NLTK。语料库包，我们有一个叫做单词的包，它包含超过20万个英语单词，你可以简单地把它们都用到你的程序中。
一旦创建你的矩阵转换成一个字符数组，并执行这段代码
import nltk
from nltk.corpus import words
from collections import Counter
def possibleWords(input, charSet):
for word in input:
dict = Counter(word)
flag = 1
for key in dict.keys():
if key not in charSet:
flag = 0
if flag == 1 and len(word)>5: #its depends if you want only length more than 5 use this otherwise remove that one.
print(word)
nltk.download('words')
word_list = words.words()
# prints 236736
print(len(word_list))
charSet = ['h', 'e', 'l', 'o', 'n', 'v', 't']
possibleWords(word_list, charSet)
输出:
eleven
eleventh
elevon
entente
entone
ethene
ethenol
evolve
evolvent
hellhole
helvell
hooven
letten
looten
nettle
nonene
nonent
nonlevel
notelet
novelet
novelette
novene
teenet
teethe
teevee
telethon
tellee
tenent
tentlet
theelol
toetoe
tonlet
toothlet
tootle
tottle
vellon
velvet
velveteen
venene
vennel
venthole
voeten
volent
volvelle
volvent
voteen
我希望你能得到它。
package ProblemSolving;
import java.util.HashSet;
import java.util.Set;
/**
* Given a 2-dimensional array of characters and a
* dictionary in which a word can be searched in O(1) time.
* Need to print all the words from array which are present
* in dictionary. Word can be formed in any direction but
* has to end at any edge of array.
* (Need not worry much about the dictionary)
*/
public class DictionaryWord {
private static char[][] matrix = new char[][]{
{'a', 'f', 'h', 'u', 'n'},
{'e', 't', 'a', 'i', 'r'},
{'a', 'e', 'g', 'g', 'o'},
{'t', 'r', 'm', 'l', 'p'}
};
private static int dim_x = matrix.length;
private static int dim_y = matrix[matrix.length -1].length;
private static Set<String> wordSet = new HashSet<String>();
public static void main(String[] args) {
//dictionary
wordSet.add("after");
wordSet.add("hate");
wordSet.add("hair");
wordSet.add("air");
wordSet.add("eat");
wordSet.add("tea");
for (int x = 0; x < dim_x; x++) {
for (int y = 0; y < dim_y; y++) {
checkAndPrint(matrix[x][y] + "");
int[][] visitedMap = new int[dim_x][dim_y];
visitedMap[x][y] = 1;
recursion(matrix[x][y] + "", visitedMap, x, y);
}
}
}
private static void checkAndPrint(String word) {
if (wordSet.contains(word)) {
System.out.println(word);
}
}
private static void recursion(String word, int[][] visitedMap, int x, int y) {
for (int i = Math.max(x - 1, 0); i < Math.min(x + 2, dim_x); i++) {
for (int j = Math.max(y - 1, 0); j < Math.min(y + 2, dim_y); j++) {
if (visitedMap[i][j] == 1) {
continue;
} else {
int[][] newVisitedMap = new int[dim_x][dim_y];
for (int p = 0; p < dim_x; p++) {
for (int q = 0; q < dim_y; q++) {
newVisitedMap[p][q] = visitedMap[p][q];
}
}
newVisitedMap[i][j] = 1;
checkAndPrint(word + matrix[i][j]);
recursion(word + matrix[i][j], newVisitedMap, i, j);
}
}
}
}
}
