java - 如何检查一个单词是否可以用一组字母拼写

Question

所以这就是我想要完成的。想象一下，你有 6 个面的积木，每个积木上都有一个字母。即{f, e, j, x, s, t}，并且您还有一个词，让我们说这个例子中的词是“食物”，您将如何检查给您的积木是否可以拼出这个词。您在单词中至少得到相同数量的块，例如“食物”这个词会给您至少 4 个块。

我已经做到了，所以每个块都创建了一个只包含可用字母的对象，例如，在单词 food 的情况下，它只包含字母 FO 或 D

String[] split = word.split("");

        for(int i = 0; i < numberOfCubes; i++){
             letterObject.put(Integer.toString(i), new validLetters());
            for(int j = 0; j < split.length; j++){
                for(int k = 0; k < 6; k++){
                    if(cubes[i][k].equalsIgnoreCase(split[j]) && !letterObject.get(Integer.toString(i)).getLetters().contains(split[j])){
                        letterObject.get(Integer.toString(i)).addLetter(split[j]);
                        System.out.println("letter added" + split[j]);
                    }
                }
            }
        }

所以我遇到的问题是你如何遍历不同的对象并检查它是否可以拼写这个词。我遇到的主要问题是，假设您有 4 个立方体，并且您正在尝试拼写食物，并且您有这些集合 {f,o,d} {f, o} {o} 和 {f} 可以拼写但是如果你只使用一个forloop，它会说它不能，因为它会在第一组中看到“f”，然后是“o”，然后是“o”，然后它不会在第四组中找到d。循环/蛮力执行所有不同方法的最佳方法是什么。

编辑：这将是一个立方体的例子，它会尝试拼出“食物”这个词

    static String[][] cubes = {
            {"f", "b", "d", "x", "o", "k"},
            {"e", "b", "o", "d", "q", "o"},
            {"f", "l", "c", "o", "e", "f"},
            {"a", "t", "c", "f", "e", "n"}
    };

上面显示的三重forloop 会抛出所有无效字母，即BXK 等，并且还删除重复项，即如果一个立方体有2 个O 类似集合2。然后它将所有这些放入它自己的对象中，该对象放入一个散列图中。在此之后，它必须使用它来检查给定的立方体是否能够拼写单词。Set 1 ({"f", "b", "d", "x", "o", "k"}) 在操作后具有 F 和 O，因此它可以放置在单词填充的第一个位置单词 food 中的 F 点，或者它可以放置在占据字母 o 的第二个或第三个位置，但它不能用于拼写“foo”，因为它每个位置只能使用一次

标签： java

Answer 1

我做了大多数人可能认为是蛮力的方法。本质上，我通过为每个块维护一个独立的索引来按顺序创建每个可能的单词。然后我将创建的单词与所需的单词进行比较。我还打印出用于构建每个成功的位置。一些额外的开销是我允许具有不同数量的面的块。最后，可能存在错误。

    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    import java.util.stream.Collectors;

    public class Blocks {

       public static void main(String[] args) {
          // input parameters
          int nBlocks = 5;
          String wordToFind = "nifty";

          // block sizes may have different number of sides
          // This permits optimization by removing irrelevant letters
          // (which I didn't do).
           String[] blockStrings = { "ffi", "rnnf", "aeif", "drst","vyxksksksksky"
           };
          // Split the blocks into a list of letter arrays
          List<String[]> blocks =
                Arrays.stream(blockStrings).map(s -> s.split("")).collect(
                      Collectors.toList());

          // turn "foobar" into abfoor"
          String[] word = wordToFind.split("");
          String sortedWord =
                Arrays.stream(word).sorted().collect(Collectors.joining());

          int count = 0;
          int[] k = new int[nBlocks];
          String[] w = new String[nBlocks];

          // calculate maximum number of iterations. The product
          // of all the block's faces for n blocks.
          int end = blocks.stream().mapToInt(a -> a.length).reduce(1,
                (a, b) -> a * b);

          for (int ii = 0; ii < end; ii++) {

             List<Integer> usedBlockPositions = new ArrayList<>();
             for (int i = 0; i < nBlocks; i++) {
                w[i] = blocks.get(i)[k[i]];
                usedBlockPositions.add(k[i]);
             }

             // compare sorted word to sorted "found" word to see if there is
             // a match.
             if (sortedWord.equals(
                   Arrays.stream(w).sorted().collect(Collectors.joining()))) {
                count++;
                System.out.println(Arrays.toString(w) + " " + usedBlockPositions);
             }

             // Bump the indices to the blocks for next try. This is used to
             // index into each block face to get the next letter. Once
             // again, this is written to allow variable faced blocks.
             // k starts out as [0,0,0,0]
             // then goes to [1,0,0,0], [2,0,0,0] etc thru to [n1,n2,n3,n4] where
             // n* is the max number of block faces for given block. The size of
             // k is the number of blocks (this shows 4).
             for (int i = 0; i < k.length; i++) {
                int v = k[i];
                if (v >= blocks.get(i).length - 1) {
                   k[i] = 0;
                }
                else {
                   k[i]++;
                   break;
                }
             }
          }
          String format = count != 1 ? "%nThere were %d combinations found.%n"
            : "%nThere was %d combination found.%n";
          System.out.printf(format, count);
       }
    }

发布的代码打印以下内容。

[f, n, i, t, y] [0, 1, 2, 3, 1]
[f, n, i, t, y] [1, 1, 2, 3, 1]
[f, n, i, t, y] [0, 2, 2, 3, 1]
[f, n, i, t, y] [1, 2, 2, 3, 1]
[i, n, f, t, y] [2, 1, 3, 3, 1]
[i, n, f, t, y] [2, 2, 3, 3, 1]
[f, n, i, t, y] [0, 1, 2, 3, 12]
[f, n, i, t, y] [1, 1, 2, 3, 12]
[f, n, i, t, y] [0, 2, 2, 3, 12]
[f, n, i, t, y] [1, 2, 2, 3, 12]
[i, n, f, t, y] [2, 1, 3, 3, 12]
[i, n, f, t, y] [2, 2, 3, 3, 12]

There were 12 combinations found.