我希望能找到解决这个问题的方向。现在，我的脑袋一直在晃动了两个星期。本质上，我要编写一个函数public static int FindWords(char[][] puzzle)，在给定2D char数组的情况下，我可以找到给定字符串集出现的次数。鉴于：
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;
}
}
例如，二维数组如下所示：
public static char[][] puzzle = {{'C','A','T'},
{'X','Z','T'},
{'Y','O','T'}};
对于以下情况，将返回8：（AT，AT，CAT，OX，TOY，T，T，T），因为我们将在水平，垂直，对角线和相反方向搜索所有相同方向。
我的方法是访问数组中的每个字符，然后使用
SearchChar函数搜索所有可能的方向...public static int FindWords(char[][] puzzle){
int arrayRow = puzzle.length;
int arrayCol = puzzle[0].length;
int found = 0;
for(int i = 0; i < arrayRow; i++){
for(int j = 0; j < arrayCol; j++){
found += SearchChar(i,j);
}
}
return found;
}
看起来像这样：
public static int SearchChar(int row, int col){
if(row < 0 || col < 0 || row > puzzle.length || col > puzzle[0].length)//Is row or col out of bounds?
return 0;
if(IsWord(puzzle[row][col]))
return 1;
return 0;
}
从概念上讲，我觉得我需要某种递归函数来处理此问题，但似乎无法解决这个问题。我什至不知道这是正确的方法。我一直在尝试
StringBuilder追加，但是我仍然在为此而苦苦挣扎。我认为此递归函数将需要使用例如puzzle[0][0]（或“ C”）并查看其是否在字典中。接着是puzzle[0][0] + puzzle[0][1]（或“ CA”），最后是puzzle[0][0] + puzzle[0][1] + puzzle[0][2]（或“ CAT”）。然后，必须垂直和对角线穿上相同的衣服。我在尝试重新进入SearchChar函数时遇到了麻烦，将位置更改附加到原始char上，以便可以查看它是否在DICTIONARY中。抱歉，这有点罗word，但我只是想给人一种我实际上正在尝试解决此问题的印象。不仅仅是一些懒惰的程序员在复制并粘贴一些问题供其他人解决。在此先感谢您的帮助！
最佳答案
我将向您展示如何逐步解决此问题。
1.从给定的拼图中生成所有可能的单词
为此，我们必须从拼图中的任何地方开始，并朝所有方向移动（除了前面的Point以外），以生成所有可能的单词；
2.为字典选择合适的数据结构
我认为Trie是一个不错的选择，适合在这种情况下使用。
选择Trie的最重要原因是，在搜索过程中，我们可以轻松地测试字典中是否存在某个单词，或者是否存在以通过搜索拼图而生成的单词开头的单词。
结果，我们可以决定是否继续搜索。
这将为我们节省大量时间，并有助于正确生成单词。
否则，我们将陷入无休止的循环...
3.实施Tire有几种实现，但是我写了自己的CharTrie：
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicIntegerFieldUpdater;
/**
* @author FaNaJ
*/
public final class CharTrie {
/**
* Pointer to root Node
*/
private final Node root = new Node();
/**
* Puts the specified word in this CharTrie and increases its frequency.
*
* @param word word to put in this CharTrie
* @return the previous frequency of the specified word
*/
public int put(String word) {
if (word.isEmpty()) {
return 0;
}
Node current = root;
for (int i = 0; i < word.length(); i++) {
current = current.getChildren().computeIfAbsent(word.charAt(i), ch -> new Node());
}
return current.getAndIncreaseFrequency();
}
/**
* @param word the word whose frequency is to be returned
* @return the current frequency of the specified word or -1 if there isn't such a word in this CharTrie
*/
public int frequency(String word) {
if (word.isEmpty()) {
return 0;
}
Node current = root;
for (int i = 0; i < word.length() && current != null; i++) {
current = current.getChildren().get(word.charAt(i));
}
return current == null ? -1 : current.frequency;
}
/**
* @param word the word whose presence in this CharTrie is to be tested
* @return true if this CharTrie contains the specified word
*/
public boolean contains(String word) {
return frequency(word) > 0;
}
/**
* @return a CharTrie Iterator over the Nodes in this CharTrie, starting at the root Node.
*/
public Iterator iterator() {
return new Iterator(root);
}
/**
* Node in the CharTrie.
* frequency-children entry
*/
private static final class Node {
/**
* the number of occurrences of the character that is associated to this Node,
* at certain position in the CharTrie
*/
private volatile int frequency = 0;
private static final AtomicIntegerFieldUpdater<Node> frequencyUpdater
= AtomicIntegerFieldUpdater.newUpdater(Node.class, "frequency");
/**
* the children of this Node
*/
private Map<Character, Node> children;
public Map<Character, Node> getChildren() {
if (children == null) {
children = new ConcurrentHashMap<>();
}
return children;
}
/**
* Atomically increments by one the current value of the frequency.
*
* @return the previous frequency
*/
private int getAndIncreaseFrequency() {
return frequencyUpdater.getAndIncrement(this);
}
}
/**
* Iterator over the Nodes in the CharTrie
*/
public static final class Iterator implements Cloneable {
/**
* Pointer to current Node
*/
private Node current;
private Iterator(Node current) {
this.current = current;
}
/**
* Returns true if the current Node contains the specified character in its children,
* then moves to the child Node.
* Otherwise, the current Node will not change.
*
* @param ch the character whose presence in the current Node's children is to be tested
* @return true if the current Node's children contains the specified character
*/
public boolean next(char ch) {
Node next = current.getChildren().get(ch);
if (next == null) {
return false;
}
current = next;
return true;
}
/**
* @return the current frequency of the current Node
*/
public int frequency() {
return current.frequency;
}
/**
* @return the newly created CharTrie Iterator, starting at the current Node of this Iterator
*/
@Override
@SuppressWarnings("CloneDoesntCallSuperClone")
public Iterator clone() {
return new Iterator(current);
}
}
}
和
WordGenerator：import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;
import java.util.function.BiConsumer;
/**
* @author FaNaJ
*/
public final class WordGenerator {
private WordGenerator() {
}
public static void generate(char[][] table, CharTrie.Iterator iterator, BiConsumer<String, Integer> action) {
final ForkJoinPool pool = ForkJoinPool.commonPool();
final VisitorContext ctx = new VisitorContext(table, action);
for (int y = 0; y < table.length; y++) {
for (int x = 0; x < table[y].length; x++) {
pool.invoke(new Visitor(new Point(x, y), null, "", iterator.clone(), ctx));
}
}
}
private static final class VisitorContext {
private final char[][] table;
private final BiConsumer<String, Integer> action;
private VisitorContext(char[][] table, BiConsumer<String, Integer> action) {
this.table = table;
this.action = action;
}
private boolean validate(Point point) {
Object c = null;
try {
c = table[point.getY()][point.getX()];
} catch (ArrayIndexOutOfBoundsException ignored) {
}
return c != null;
}
}
private static final class Visitor extends RecursiveAction {
private final Point current;
private final Point previous;
private final CharTrie.Iterator iterator;
private final VisitorContext ctx;
private String word;
private Visitor(Point current, Point previous, String word, CharTrie.Iterator iterator, VisitorContext ctx) {
this.current = current;
this.previous = previous;
this.word = word;
this.iterator = iterator;
this.ctx = ctx;
}
@Override
protected void compute() {
char nextChar = ctx.table[current.getY()][current.getX()];
if (iterator.next(nextChar)) {
word += nextChar;
int frequency = iterator.frequency();
if (frequency > 0) {
ctx.action.accept(word, frequency);
}
List<Visitor> tasks = new ArrayList<>();
for (Direction direction : Direction.values()) {
Point nextPoint = direction.move(current);
if (!nextPoint.equals(previous) && ctx.validate(nextPoint)) {
tasks.add(new Visitor(nextPoint, current, word, iterator.clone(), ctx));
}
}
invokeAll(tasks);
}
}
}
}
请注意，我已经使用
ForkJoinPool和RecursiveAction加快了搜索速度。学到更多 ：
https://docs.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html
http://tutorials.jenkov.com/java-util-concurrent/java-fork-and-join-forkjoinpool.html
http://www.javaworld.com/article/2078440/enterprise-java/java-tip-when-to-use-forkjoinpool-vs-executorservice.html
其余课程：
PuzzleSolverimport java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.BiConsumer;
import java.util.stream.Stream;
/**
* @author FaNaJ
*/
public final class PuzzleSolver {
private final CharTrie dictionary;
public enum OrderBy {FREQUENCY_IN_DICTIONARY, FREQUENCY_IN_PUZZLE}
public PuzzleSolver(CharTrie dictionary) {
this.dictionary = dictionary;
}
public CharTrie getDictionary() {
return dictionary;
}
public Stream<Word> solve(char[][] puzzle) {
return solve(puzzle, OrderBy.FREQUENCY_IN_DICTIONARY);
}
public Stream<Word> solve(char[][] puzzle, OrderBy orderBy) {
Stream<Word> stream = null;
switch (orderBy) {
case FREQUENCY_IN_DICTIONARY: {
final Map<String, Integer> words = new ConcurrentHashMap<>();
WordGenerator.generate(puzzle, dictionary.iterator(), words::put);
stream = words.entrySet().stream()
.map(e -> new Word(e.getKey(), e.getValue()));
break;
}
case FREQUENCY_IN_PUZZLE: {
final Map<String, AtomicInteger> words = new ConcurrentHashMap<>();
BiConsumer<String, Integer> action = (word, frequency) -> words.computeIfAbsent(word, s -> new AtomicInteger()).getAndIncrement();
WordGenerator.generate(puzzle, dictionary.iterator(), action);
stream = words.entrySet().stream()
.map(e -> new Word(e.getKey(), e.getValue().get()));
break;
}
}
return stream.sorted((a, b) -> b.compareTo(a));
}
}
http://winterbe.com/posts/2014/07/31/java8-stream-tutorial-examples/
Pointimport java.util.Objects;
/**
* @author FaNaJ
*/
public final class Point {
private final int x;
private final int y;
public Point() {
this(0, 0);
}
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
@Override
public int hashCode() {
return x * 31 + y;
}
@Override
public boolean equals(Object obj) {
if (obj == this) {
return true;
}
if (obj == null || getClass() != obj.getClass()) {
return false;
}
Point that = (Point) obj;
return x == that.x && y == that.y;
}
@Override
public String toString() {
return "[" + x + ", " + y + ']';
}
}
Word/**
* @author FaNaJ
*/
public final class Word implements Comparable<Word> {
private final String value;
private final int frequency;
public Word(String value, int frequency) {
this.value = value;
this.frequency = frequency;
}
public String getValue() {
return value;
}
public int getFrequency() {
return frequency;
}
@Override
public int hashCode() {
return value.hashCode() * 31 + frequency;
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
Word that = (Word) o;
return frequency == that.frequency && value.equals(that.value);
}
@Override
public String toString() {
return "{" +
"value='" + value + '\'' +
", frequency=" + frequency +
'}';
}
@Override
public int compareTo(Word o) {
return Integer.compare(frequency, o.frequency);
}
}
Direction/**
* @author FaNaJ
*/
public enum Direction {
UP(0, 1), UP_RIGHT(1, 1), UP_LEFT(-1, 1),
RIGHT(1, 0), LEFT(-1, 0),
DOWN(0, -1), DOWN_RIGHT(1, -1), DOWN_LEFT(-1, -1);
private final int x, y;
Direction(int x, int y) {
this.x = x;
this.y = y;
}
public Point move(Point point) {
return new Point(point.getX() + x, point.getY() + y);
}
}
4.测试
/**
* @author FaNaJ
*/
public class Test {
public static String[] DICTIONARY = {"OX", "CAT", "TOY", "AT", "DOG", "CATAPULT", "T", "AZOYZACZOTACXY"};
public static void main(String[] args) {
CharTrie trie = new CharTrie();
for (String word : DICTIONARY) {
trie.put(word);
}
PuzzleSolver solver = new PuzzleSolver(trie);
char[][] puzzle = {
{'C', 'A', 'T'},
{'X', 'Z', 'T'},
{'Y', 'O', 'T'}
};
solver.solve(puzzle, PuzzleSolver.OrderBy.FREQUENCY_IN_PUZZLE).forEach(System.out::println);
}
}
输出：
{value='T', frequency=3}
{value='AT', frequency=2}
{value='CAT', frequency=2}
{value='TOY', frequency=2}
{value='OX', frequency=1}
{value='AZOYZACZOTACXY', frequency=1}