未从字典返回有效单词

xt0899hw  于 2021-07-04  发布在  Java
关注(0)|答案(1)|浏览(339)

下面是我的代码片段:package com.dynamicprogramming;

import java.util.ArrayList;
import java.util.List;

public class BoogleProblem {

    public static int[] Path_Row = {0, 0, 1, 1, -1, 1, -1, -1};
    public static int[] Path_Col = {1, -1, -1, 1, 1, 0, 0, -1};

    public static void findWord(char[][] board, boolean[][] visited, int row, int col, String word, 
                         List<String> englishDictionary) {
        if (englishDictionary.contains(word)) {
            System.out.println(word);
        }

        if (board.length == word.length()) {
            return;
        }

        visited[row][col] = true;

        for (int index = 0 ; index < board.length; index++) {
             int rowNew = row + Path_Row[index];
             int colNew = col + Path_Col[index];
             if (ifValid(rowNew, colNew, visited)) {
                 visited[rowNew][colNew] = true;
                 findWord(board, visited, rowNew, colNew, word + board[rowNew][colNew], englishDictionary);
                 // Backtracking logic goes here
                 visited[rowNew][colNew] = false;
             }
        }
    }

    public static boolean ifValid(int row, int col, boolean[][] visited) {
            if ((row >= 0) && (row < 3) && (col >= 0) && (col < 3) && !visited[row][col]) {
               return true;
            } else {
               return false;
            }
    }

    public static void main(String[] args) {
        char[][] board = {{'G', 'I', 'Z'},
                          {'U', 'E', 'K'},
                          {'Q', 'S', 'E'}};

        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length ; i++) {
            for (int j = 0; j < board[0].length; j++) {
                visited[i][j] = false;
            }
        }

        List<String> englishDictionary = new ArrayList<String>();
        englishDictionary.add("GEEKS");
        englishDictionary.add("QUIZ");
        englishDictionary.add("FOR");
        englishDictionary.add("GO");

        String word = "";
        for (int i = 0; i < board.length; i++) {
            for (int j = 0 ; j < board[0].length; j++) {
                 findWord(board, visited, 0, 0, word + board[i][j], englishDictionary);
            }
        }
    }
}

这是行不通的&什么也没做。正如我所观察到的,在字符串多于2个字符的大多数情况下,ifvalid()方法都返回false。请告诉我,这里出了什么问题。

fdbelqdn

fdbelqdn1#

试试这个。

public static int[] Path_Row = {0, 0, 1, 1, -1, 1, -1, -1};
public static int[] Path_Col = {1, -1, -1, 1, 1, 0, 0, -1};

public static void findWord(char[][] board, boolean[][] visited, int row, int col, String word,
                     List<String> englishDictionary) {
    if (englishDictionary.contains(word)) {
        System.out.println(word);
    }

//  if (board.length == word.length()) {                        // DELETE
//      return;                                                 // DELETE
//  }                                                           // DELETE

    visited[row][col] = true;

//  for (int index = 0 ; index < board.length; index++) {       // CHANGE
    for (int index = 0 ; index < Path_Row.length; index++) {    // CHANGE
         int rowNew = row + Path_Row[index];
         int colNew = col + Path_Col[index];
         if (ifValid(rowNew, colNew, visited)) {
             visited[rowNew][colNew] = true;
             findWord(board, visited, rowNew, colNew, word + board[rowNew][colNew], englishDictionary);
             // Backtracking logic goes here
             visited[rowNew][colNew] = false;
         }
    }
    visited[row][col] = false;                                  // ADD
}

public static boolean ifValid(int row, int col, boolean[][] visited) {
        if ((row >= 0) && (row < 3) && (col >= 0) && (col < 3) && !visited[row][col]) {
           return true;
        } else {
           return false;
        }
}

public static void main(String[] args) {
    char[][] board = {{'G', 'I', 'Z'},
                      {'U', 'E', 'K'},
                      {'Q', 'S', 'E'}};

    boolean[][] visited = new boolean[board.length][board[0].length];
    for (int i = 0; i < board.length ; i++) {
        for (int j = 0; j < board[0].length; j++) {
            visited[i][j] = false;
        }
    }

    List<String> englishDictionary = new ArrayList<String>();
    englishDictionary.add("GEEKS");
    englishDictionary.add("QUIZ");
    englishDictionary.add("FOR");
    englishDictionary.add("GO");

    String word = "";
    for (int i = 0; i < board.length; i++) {
        for (int j = 0 ; j < board[0].length; j++) {
 //          findWord(board, visited, 0, 0, word + board[i][j], englishDictionary);  // CHANGE
             findWord(board, visited, i, j, word + board[i][j], englishDictionary);  // CHANGE
        }
    }
}

输出

GEEKS
QUIZ

相关问题