在拼字游戏中获得单词的位置

Question

我正在使用这段代码解决Android中的4 *4 boggle。它工作得很好，但是我想知道找到的单词在其中的位置。

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

---

字类:

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