java - 在二维字符数组中搜索事件

Question

我希望能为我遇到的这个问题找到一些方向。两周以来我一直在为此苦思冥想。本质上，我要编写一个函数，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 函数时遇到问题，将位置更改附加到原始字符，以便我可以查看它是否在 DICTIONARY 中。

抱歉，如果这有点罗嗦，但我只是想给人一种印象，我实际上正在努力解决这个问题。不仅仅是一些懒惰的程序员将一些问题复制并粘贴到这里以供其他人解决。在此先感谢您的帮助!

Answer 1

我将逐步向您展示如何解决这个问题。

1。从给定的拼图中生成所有可能的单词

要做到这一点，我们必须从拼图中的任何地方开始，向所有方向(除了前面的点)移动，以生成所有可能的单词；

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

其余类(class):

解谜

import 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/

点

import 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);
    }

}

方向

/**
 * @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}