#java #arrays #recursion #multidimensional-array
#java #массивы #рекурсия #многомерный массив
Вопрос:
Я пытаюсь выяснить, как рекурсивно искать слово в массиве символов и возвращать его, если оно есть или отсутствует. Думайте об этом как о программном эквиваленте поиска по слову. Мой текущий код приведен ниже. Начальное значение 9999 полезно для тестирования. Как мне написать метод рекурсивного поиска для проверки наличия любого заданного слова в массиве символов?
public class Board {
private char[][] board = new char[4][4];
private boolean[][] visited = new boolean[4][4];
private String word;
public Board(int seed){
word = "";
Random rand = new Random(seed);
for(int i = 0; i < board.length; i ){
for(int j = 0; j < board[0].length; j ){
char randomChar = (char) (rand.nextInt(27) 65);
//System.out.print(" " randomChar " ");
board[i][j] = randomChar;
//System.out.print(board[i][j]);
}//System.out.println();
}
}
public void resetBoard(){
for(int i = 0; i < board.length; i ){
for(int j = 0; j < board[0].length; j ){
visited[i][j] = false;
}
}
}
public void printBoard(){
for(int i = 0; i < board.length; i ){
for(int j = 0; j < board[0].length; j ){
if(j == 0)
System.out.println(" --- --- --- --- ");
System.out.print("| " board[i][j] " | ");
}
System.out.println("n --- --- --- --- ");
}
}
public boolean verifyWord(String w){
this.word = w;
for(int i = 0; i < w.length(); i ){
// char letter = w.charAt(i);
// System.out.println(letter);
boolean wordVerify = verifyWordRecursively(0, 0, 0);
if(wordVerify == true)
return true;
// if(i == w.length() - 1){
// if(wordVerify == true)
// return true;
// }
}return false;
}
public boolean verifyWordRecursively(int wordIndex, int row, int col){
char letter = word.charAt(wordIndex);
System.out.println(letter);
if(board[row][col] == letter){
return true;
}
else{
if(col 1 < board[0].length){
verifyWordRecursively(wordIndex, row, col 1);
}
if(row 1 < board.length){
verifyWordRecursively(wordIndex, row 1, col);
}
}return false;
}
}
Вот мой основной класс:
public class LA2Main {
public static void main(String[] args) throws IOException{
int seed = getSeed();
Board b = new Board(seed);
b.printBoard();
Scanner inFile = new Scanner(new FileReader("input.txt"));
// while(inFile.hasNextLine()){
// System.out.println(inFile.nextLine());
String word = inFile.nextLine();
b.resetBoard();
System.out.println("-----------------------n" word);
boolean isVerified = b.verifyWord(word);
if(isVerified == true)
System.out.println("'" word "' was found on the board!");
else
System.out.println("'" word "' is NOT on this board");
b.printBoard();
// }
}
public static int getSeed(){
Scanner sc = new Scanner(System.in);
int userInput;
while(true){
try{
System.out.println("Enter an integer seed value greater than 0: ");
userInput = Integer.parseInt(sc.next());
if( userInput > 0)
return userInput;
}
catch(NumberFormatException e){
System.out.println("Invalid!");
}
}
}
}
Комментарии:
1. Я бы, вероятно, сделал это с помощью итерации, а не рекурсии. Я говорю это потому, что, похоже, существует много угловых случаев, и объем информации, которую вам нужно будет передать вашей рекурсивной функции, станет громоздким. Т.Е. Сначала вы просто хотите проверить, является ли буква вашего at первой в слове, затем вы проверяете буквы вокругэто будет следующим, а затем после этого вам нужно двигаться в том же направлении, в котором указаны первые 2 буквы. Это, конечно, возможно, но итерация, похоже, подходит для моей книги.
Ответ №1:
Самый простой способ найти слово в массиве символов, вероятно, сначала преобразовать его в a String , а затем использовать contains как next нет необходимости изобретать велосипед:
boolean contains = new String(myCharArray).contains(myWord);
Это самый простой способ, который есть case sensitive и будет возвращаться true , если слово является всего лишь составной частью более крупного слова, поэтому более подходящим было бы использовать matches регулярное выражение без учета регистра, которое определяет границы слова, как показано ниже:
boolean contains = new String(myCharArray).matches(
String.format("(?i)^.*\b%s\b.*$", Pattern.quote(myWord))
);
Ответ №2:
Итак, я предполагаю, что вопрос касался рекурсивного сопоставления строк, которое, хотя и указывалось ранее, может быть не лучшим способом, все же можно использовать.
Глядя на ваш код, вы не хотите сопоставлять с массивом символов, а скорее с матрицей символов. Давайте воспользуемся наивным подходом, поскольку мы все равно находимся на неэффективном пути.
Я приведу некоторый псевдокод, давайте начнем с некоторого кода, который проверяет, соответствует ли матрица массиву с определенным смещением:
function matches(char matrix[][], char needle[], int row, int col)
width, height = dimensions(matrix)
/* Check whether we're out of range */
if (width * height < row * width col length(needle)) {
return false
}
for (int i = 0 ... len(needle)) {
if (matrix[row][col] != needle[i]) {
return false
}
/* increment position, (hint: integer division) */
row = (col 1) / width
col = (col 1) % width
}
return true
Теперь это все еще не рекурсивное решение, и функция имеет много аргументов (не очень хорошо для ясности кода). Давайте сначала напишем оболочку:
function matches(char matrix[][], char needle[])
recursiveMatches(matrix, needle, 0, 0)
recursiveMatches должен отслеживать исходную строку и столбец,
чтобы выполнить правильный рекурсивный вызов. И, конечно, ему нужен рекурсивный вызов, при котором он потерпел бы неудачу раньше:
function recursiveMatches(char matrix[][], char needle[], int row, int col)
width, height = dimensions(matrix)
originalRow, originalCol = row, col
/* Check whether we're out of range */
if (width * height < row * width col length(needle)) {
return false
}
for (int i = 0 ... len(needle)) {
if (matrix[row][col] != needle[i]) {
/* add one to the position */
originalRow = (originalCol 1) / width
originalCol = (originalCol 1) % width
return recursiveMatches(matrix, needle, originalRow, originalCol)
}
/* increment position */
row = (col 1) / width
col = (col 1) % width
}
return true
Надеюсь, преобразование этого в правильный java-код не должно оказаться слишком сложным.