将给定的单词沿对角线方向搜索到字母拼图中

Question

我有一个用随机字母填充的二维数组。我要在那个数组中找到单词。

我写了一个 toString 方法，它使用：

startX : 待查找字符串的起始X位置
startY : 待查找字符串的起始Y位置
endX : 待查找String的结束X位置
endY : 待查找字符串的结束Y位置

我提供的代码可以水平和垂直工作，但不适用于对角线。如何打印排列在对角线上的单词？

@Override
public String toString() {
    StringBuilder sb = new StringBuilder();

    if (startX == endX) {
        if (startY < endY) {
            for (int i = startY; i <= endY; i++)
                sb.append(i).append("x").append(startY).append("  ");
        } else {
            for (int i = endY; i <= startY; i++)
                sb.append(i).append("x").append(startY).append("  ");
        }
    }
    if (startY == endY) {
        if (startX < endX) {
            for (int i = startX; i <= endX; i++)
                sb.append(i).append("x").append(startY).append("  ");
        } else
            for (int i = endX; i <= startX; i++)
                sb.append(i).append("x").append(startY).append("  ");
    }
    if (startX > endX && startY > endY) {
        int i = startX;
        int j = startY;
        while (i >= endX)
            sb.append(i--).append("x").append(j--).append("  ");
    } else if (startX > endX && startY < endY) {
        int i = startX;
        int j = startY;
        while (i >= endX)
            sb.append(i--).append("x").append(j++).append("  ");
    } else if (startX < endX && startY > endY) {
        int i = startX;
        int j = startY;
        while (i >= endX)
            sb.append(i++).append("x").append(j--).append("  ");
    } else if (startX < endX && startY < endY) {
        int i = startX;
        int j = startY;
        while (i >= endX)
            sb.append(i++).append("x").append(j++).append("  ");
    }

    return sb.toString();
}

Answer 1

如果：

你的每个词都在特定的行中，不会溢出到下一行并且
所有单词都是连续的

那么你可以这样做：

@Override
public String toString()
{
    StringBuilder string = new StringBuilder();

    for(int c = startY; c<=endY; c++) {
        string.append(startX).append("x").append(c).append(", ");
    }

    return string.toString();
}

Answer 2

我假设您正在寻找的是一种在字母拼图中找到单词的方法。

在这种情况下，我建议您将拼图存储在一个二维数组中，将要查找的单词存储在一个字符串中。然后你需要检查数组中所有与你要查找的字符串的起始字符具有相同字符的位置（在我提供的代码中：findWord）。找到匹配项后，您需要检查字符串的其余字符（在我提供的代码中：checkDirections）。如果其余字符匹配，那么您就找到了字符串，否则您需要检查其他方向或字符串第一个字母的下一次出现。

接下来我提供代码：

package letterPuzzle;

import java.util.Random;


public class LetterPuzzle {

private static final String ALPHABET = "abcdefghijklmnopqrstuvwxyz";
private static final int[] DIRECTIONS_X = new int[] { 0, 0, 1, -1, 1, 1, -1, -1 };
private static final int[] DIRECTIONS_Y = new int[] { 1, -1, 0, 0, 1, -1, 1, -1 };

private static int N;
private static char[][] puzzle;


private static void initializePuzzle() {
    Random r = new Random();
    puzzle = new char[N][N];
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            puzzle[i][j] = ALPHABET.charAt(r.nextInt(ALPHABET.length()));
        }
    }

    // Add the JAVA word in a location
    if (N < 6) {
        System.out.println("[ERRRO] Example needs N >= 6");
        System.exit(1);
    }
    puzzle[2][3] = 'j';
    puzzle[3][3] = 'a';
    puzzle[4][3] = 'v';
    puzzle[5][3] = 'a';
}

private static void printPuzzle() {
    System.out.println("[DEBUG] Puzzle");
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            System.out.print(puzzle[i][j] + " ");
        }
        System.out.println("");
    }
    System.out.println("[DEBUG] End Puzzle");
}

private static boolean findWord(String word) {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            // We check all the matrix but only try to match the word if the first letter matches
            if (puzzle[i][j] == word.charAt(0)) {
                if (checkDirections(i, j, word)) {
                    return true;
                }
            }
        }
    }

    return false;
}

private static boolean checkDirections(int initX, int initY, String word) {
    System.out.println("Searching " + word + " from (" + initX + ", " + initY + ")");
    // Checks the different directions from (initX, initY) position
    for (int dirIndex = 0; dirIndex < DIRECTIONS_X.length; ++dirIndex) {
        System.out.println("  - Searching direction " + dirIndex);
        boolean wordMatches = true;
        // Checks all the characters in an specific direction
        for (int charIndex = 0; charIndex < word.length() && wordMatches; ++charIndex) {
            int x = initX + DIRECTIONS_X[dirIndex] * charIndex;
            int y = initY + DIRECTIONS_Y[dirIndex] * charIndex;
            System.out.println("    -- Checking position (" + x + ", " + y + ")");
            if (x < 0 || y < 0 || x >= N || y >= N || puzzle[x][y] != word.charAt(charIndex)) {
                System.out.println("    -- Not match");
                wordMatches = false;
            } else {
                System.out.println("    -- Partial match");
            }
        }

        // If the word matches we stop, otherwise we check other directions
        if (wordMatches) {
            return true;
        }
    }

    return false;
}

public static void main(String[] args) {
    // Check args
    if (args.length != 2) {
        System.err.println("[ERROR] Invalid usage");
        System.err.println("[ERROR] main <puzzleSize> <wordToSearch>");
    }

    // Get args
    N = Integer.valueOf(args[0]);
    String word = args[1];

    // Initialize puzzle (randomly)
    initializePuzzle();
    printPuzzle();

    // Search word
    boolean isPresent = findWord(word);
    if (isPresent) {
        System.out.println("Word found");
    } else {
        System.out.println("Word NOT found");
    }
}

}

注意：

拼图矩阵是随机初始化的，我在 2,3 -> 5,3 位置硬编码了单词 'java'（这只是为了示例，但您应该初始化拼图从命令行或文件）。
ALPHABET 变量仅用于随机生成。
方向存储在两个一维数组中，以编程方式生成 8 个方向，但为了清楚起见，您可以展开。
就性能而言，这可能不是最高效的代码，因为如果字符串的第一个字符出现多次，您将仔细检查很多位置。然而，它仍然是一个可行且简单的解决方案。

将给定的单词沿对角线方向搜索到字母拼图中

search a given word into a letter puzzle diagonally

java

tostring