获取单词在 Boggle 中的位置

Question

我正在使用这段代码解决 Android 中的 4 *4 问题。它运行良好，但我正在尝试获取其中找到的单词的位置。

| A | C | E | X |
-----------------
| X | X | X | X |
-----------------
| X | X | X | X |
-----------------
| X | B | A | R |

假设我正在尝试根据 0 索引查找 ACE 的位置。它是 [0, 1, 2]。

或者 BAR，它是 [13, 14, 15]

我怎样才能做到这一点？我尝试了一些实现，但它搞砸了，所以我发布了没有它们的代码。

public class Boggle {

    private NavigableSet<String> dict___ = new TreeSet<>();
    ArrayList<Word> foundWords = new ArrayList<>();

    /* helpers */
    int N = 4;
    char[][] board = new char[N][N];


    /* context obj*/
    private final Context ctx;

    public Boggle(Context ctx) {
        this.ctx = ctx;
        initFile();
    }


    public ArrayList<Word> startSolving(String str) {
        initPuzzle(str);

        Stack<Point> visitedLetters = new Stack<>();


        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                findWordRecursive(i, j, new Word("", null), visitedLetters);
            }
        }

        Log("foundWords = " + foundWords.size());
        Log("=============================");

        return foundWords;
    }

    private void findWordRecursive(int i, int j, Word prefix, Stack<Point> visitedLetters) {

        Point currentLocation = new Point(i, j);
        visitedLetters.push(currentLocation);

        String possibleWord = prefix.getWord() + this.board[i][j];

        if (dict___.contains(possibleWord)) {
            if(!isFoundWordsContains(possibleWord)) {
                foundWords.add(
                        new Word(
                                possibleWord,
                                null)
                );
            }
        }

        NavigableSet<String> child__ = findChildWords(possibleWord);

        if (!child__.isEmpty()) {
            for (int x = Math.max(0, i - 1); x < Math.min(i + 2, 4); x++) {
                for (int y = Math.max(0, j - 1); y < Math.min(j + 2, 4); y++) {
                    if (!visitedLetters.contains(new Point(x,y))) {
                        findWordRecursive(x, y, new Word(possibleWord, null), visitedLetters);
                    }
                }
            }
        }

        visitedLetters.pop();
    }

    private void initFile() {

        Log("=============================");
        Log("init starting");

        //fill dict___ array with words from a TXT file.

        Log("init finished")

    }


    void initPuzzle(String letters) {
        letters = letters.toLowerCase(new Locale("tr", "TR"));
        int in = 0;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {

                board[i][j] = letters.charAt(in);
                in++;
            }
        }
        Log("board letters inited");
    }

    void Log(String e){
         Log.wtf("___Boggle___", e);
    }

    NavigableSet<String> findChildWords(String prefix){
        prefix = prefix.toLowerCase(new Locale("tr", "TR"));
        return dict___.subSet(prefix, false, prefix+"zzzzzzzzzzzzzzz", false);
    }

    boolean isFoundWordsContains(String word) {
        boolean yeah = false;

        for (int i = 0; i < foundWords.size(); i++) {
            if(word.equals(foundWords.get(i).getWord())) {
                yeah = true;
                break;
            }
        }

        return yeah;
    }
}

单词class:

public class Word {

    private String word;
    private ArrayList<Integer> position;

    public Word(String word, ArrayList<Integer> position) {
        this.word = word;
        this.position = position;
    }

    public String getWord() {
        return word;
    }

}

Answer 1

我认为你的问题是因为 prefix = prefix.toLowerCase(new Locale("tr", "TR"));

因此，为了让您的代码正常工作，您可能需要检查以下步骤：

dict___中的所有String必须小写。
dict___ 必须包含单词子集（对于 "ace"，必须至少有 "a"、"ac"、"ace"）
在 findWordRecursive 中将 String possibleWord = prefix.getWord() + this.board[i][j]; 替换为
String possibleWord = prefix.getWord() + this.board[i][j]; possibleWord = possibleWord.toLowerCase();
更新
要找到位置，你可以试试这个：
在startSolving中，使用findWordRecursive(i, j, new Word("", new ArrayList<Integer>()), visitedLetters);

在findWordRecursive中，添加pass currentPosition

    int curPos = i * N + j;
    if (dict___.contains(possibleWord)) {
        if(!isFoundWordsContains(possibleWord)) {
            // add current position to the word
            ArrayList<Integer> posList = new ArrayList<Integer>();
            posList.addAll(prefix.position);
            posList.add(curPos);
            foundWords.add(
                    new Word(
                            possibleWord,
                            posList)
            );
        }
    }

    NavigableSet<String> child__ = findChildWords(possibleWord);

    if (!child__.isEmpty()) {
        for (int x = Math.max(0, i - 1); x < Math.min(i + 2, 4); x++) {
            for (int y = Math.max(0, j - 1); y < Math.min(j + 2, 4); y++) {
                if (!visitedLetters.contains(new Point(x,y))) {
                    // add current before find new word
                    ArrayList<Integer> posList = new ArrayList<Integer>(prefix.position);
                    posList.addAll(prefix.position);
                    posList.add(curPos);

                    findWordRecursive(x, y, new Word(possibleWord, posList), visitedLetters);
                }
            }
        }
    }

获取单词在 Boggle 中的位置

Get position of word in Boggle

java

android

boggle