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

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} 可以拼写但如果你只使用一个for循环，它会说它不能，因为它会在第一组中看到“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）。然后它将所有这些放入自己的对象中，该对象放入哈希图中。之后，它必须使用它来检查给定的立方体是否能够拼写该单词。集合 1 ({"f", "b", "d", "x", "o", "k"}) 在操作后具有 F 和 O，因此它可以放置在单词填充的第一个槽处food 一词中的 F 点，也可以放在占据字母 o 的第二个或第三个插槽中，但不能用于拼写“foo”，因为每个插槽只能使用一次

Answer 1

我做了大多数人可能认为是蛮力方法的事情。本质上，我通过为每个块维护一个独立的索引来按顺序创建每个可能的单词。然后我将创建的词与所需的词进行比较。我还打印出用于构建每个成功的位置。一些额外的开销是我允许具有不同面数的块。最后，可能存在错误。&nbsp; &nbsp; import java.util.ArrayList;&nbsp; &nbsp; import java.util.Arrays;&nbsp; &nbsp; import java.util.List;&nbsp; &nbsp; import java.util.stream.Collectors;&nbsp; &nbsp; public class Blocks {&nbsp; &nbsp; &nbsp; &nbsp;public static void main(String[] args) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // input parameters&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int nBlocks = 5;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; String wordToFind = "nifty";&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // block sizes may have different number of sides&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // This permits optimization by removing irrelevant letters&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // (which I didn't do).&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;String[] blockStrings = { "ffi", "rnnf", "aeif", "drst","vyxksksksksky"&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;};&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // Split the blocks into a list of letter arrays&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; List<String[]> blocks =&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Arrays.stream(blockStrings).map(s -> s.split("")).collect(&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Collectors.toList());&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // turn "foobar" into abfoor"&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; String[] word = wordToFind.split("");&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; String sortedWord =&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Arrays.stream(word).sorted().collect(Collectors.joining());&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int count = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int[] k = new int[nBlocks];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; String[] w = new String[nBlocks];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // calculate maximum number of iterations. The product&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // of all the block's faces for n blocks.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int end = blocks.stream().mapToInt(a -> a.length).reduce(1,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (a, b) -> a * b);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int ii = 0; ii < end; ii++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;List<Integer> usedBlockPositions = new ArrayList<>();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for (int i = 0; i < nBlocks; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; w[i] = blocks.get(i)[k[i]];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; usedBlockPositions.add(k[i]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// compare sorted word to sorted "found" word to see if there is&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// a match.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if (sortedWord.equals(&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Arrays.stream(w).sorted().collect(Collectors.joining()))) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println(Arrays.toString(w) + " " + usedBlockPositions);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// Bump the indices to the blocks for next try. This is used to&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// index into each block face to get the next letter. Once&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// again, this is written to allow variable faced blocks.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// k starts out as [0,0,0,0]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// then goes to [1,0,0,0], [2,0,0,0] etc thru to [n1,n2,n3,n4] where&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// n* is the max number of block faces for given block. The size of&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// k is the number of blocks (this shows 4).&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for (int i = 0; i < k.length; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int v = k[i];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (v >= blocks.get(i).length - 1) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;k[i] = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;k[i]++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; String format = count != 1 ? "%nThere were %d combinations found.%n"&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; : "%nThere was %d combination found.%n";&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.printf(format, count);&nbsp; &nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; }发布的代码打印以下内容。[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.

Answer 2

我不完整的想法如下：块放在一个数组中，它的索引作为每个块的唯一标识。然后你构建一个列表映射：Map<String, List<Integer>>其中键是目标单词中字母的出现（因此对于单词“food”，字母“o”应该在映射中出现两次，比如键值"o1" "o2"）中的值地图是包含字母的块列表。构建此数据结构后，您需要在映射中的值中搜索一组唯一的整数值。编辑：所以这些块已经在数组中表示了。所以第一个块，其中的块cubes[0]将有一个 id 值0，依此类推。对于“食物”这个词，您构建了一个包含四个条目的地图。键是："f1"、"o1"、"o2"、"d1"。使用这些数字是为了让您可以在地图上多次放置同一个字母。确定键后，您将在所有块上循环，对于每个块的所有字母，对于您查看的每个字母，如果它是目标单词的一部分。如果是，则将块的 id（在 中的索引cubes，还记得吗？）添加到映射中的值列表中。完成后你将得到以下映射"f1" -> [0,2,3]&nbsp; // blocks 0,2,3 contain 'f'"o1" -> [0,1,2]"o2" -> [0,1,2]"d1" -> [0,1]现在你在值（整数列表）上循环并寻找一组从每个映射条目中获取的唯一整数值。例如集合 3,1,2,0（3 取自第一个地图条目，1 来自第二个地图条目，依此类推）-> 集合就是答案。

Answer 3

String[] split = word.split("");Set<String> mySet = new HashSet<>(split);for(int i = 0; i < numberOfCubes; i++) {&nbsp; &nbsp; //get cube&nbsp; &nbsp; &nbsp;for(int k = 0; k < 6; k++){&nbsp; &nbsp; &nbsp; &nbsp; //loop through each value in the cube and try to remove it from the set&nbsp; &nbsp; &nbsp; &nbsp; set.remove(cube[k]);&nbsp;&nbsp; &nbsp; &nbsp;}}if mySet length = 0; return true;//i.e. cubes can create the word