java - CodeEval 字母 block 挑战

Question

我正在参与 CodeEval 挑战，以下是其描述:

挑战描述:

我们都记得小时候学习如何使用字母 block 组成不同的单词，例如 MOM、DAD、TRAIN 等。我们建议你暂时提醒一下这个时候，想象一下自己是个 child 。所以，你有一组字母 block 。每个方 block 的六个面上都有一个字母。此外，您还想组合一个与您的童年相关的单词。编写一个程序来验证是否可以从集合中形成必要的单词。如果是，则将“True”打印到标准输出；否则，打印“False”。您只能从字母 block 中选择一个字母，并以任意顺序放置 block 。

输入样本:

第一个参数是文件的路径。每行包含测试用例，这些测试用例具有由管道符号“|”分隔的三个参数。1. 该行中的第一个参数是一个数字，显示集合中有多少个 block 。2. 第二个是你要组成的单词。3. 第三个是字母数组列表。字母 block 的一个面包含数组中的一个字母。例如:有一个字母数组“ABCDEF”。它是指具有以下面的一个玩具积木:“A”、“B”、“C”、“D”、“E”、“F”。

4 | DOG | UPZRHR INOYLC KXDHNQ BAGMZI

6 | HAPPY | PKMFQP KTXGCV OSDMAJ SDSIMY OEPGLE JZCDHI

5 | PLAIN | BFUBZD XMQBNM IDXVCN JCOIAM OZYAYH

输出示例:

True
True
False

由于某种原因，我的代码部分通过，有人可以告诉我我做错了什么吗？这是我的代码:

public class AlphabetBlocks {

public static void main(String[] args) {
    File file = new File(args[0]);
    BufferedReader buffer = new BufferedReader(new FileReader(file));
    String line;
    while ((line = buffer.readLine()) != null) {
        line = line.trim();
        String[] separate = line.split(" \\| ");

        String[] blocks = separate[2].split("\\s+");
        separate[1] = separate[1].trim();

        for (int i = 0; i < separate[1].length(); i++) {
            for (int j = 0; j < blocks.length; j++) {
                if (blocks[j].contains(separate[1].toUpperCase().charAt(i)+"")) {
                    blocks[j]="";
                    separate[1] = separate[1].replaceFirst(separate[1].charAt(i)+"", "0");
                    break;
                }
            }
        }
        if (separate[1].matches("\\d+")) {
            System.out.println("True");
        } else {
            System.out.println("False");
        }
   }
 }
}

Answer 1

让我们考虑这个问题的二维矩阵表，其中 -

• 行的大小与童年字符串相同。我们称之为n。
• 列等于字母 block 的总数。 (实现例1、2和3中的4、6、5)。我们称之为m。它们基本上是要检查的字符串数量。

在n x m二维 boolean 矩阵中，如果字符串的第第个字符出现在第j block 中，我们标记table[i][j] = true; 否则标记为 false。我在第一个示例中使用了下图。

_ | UPZRHR | INOYLC | KXDHNQ | BAGMZI
D | false  | false  | true   | false
O | false  | true   | false  | false
G | false  | false  | false  | true

现在，一个 block 可以满足童年字符串的所有字母。但对于童年字符串中的每个字符，我们都需要一个不同的字母 block 。

我们该如何解决这个问题？好吧，对于每个 table[i][j] = true，我们将 i 和 j 存储在 2 个单独的集合中，i 在行集中，j 在列集中。

行集的大小应完全等于童年字符串的大小。这意味着童年字符串中的每个字符都可以在字母 block 之一中找到。
列集的大小应大于或等于童年字符串的大小。这意味着我们能够从不同的字母 block 中生成字符串。

如果不满足上述条件，我们就无法制作我们的童年字符串。

下面是c++中的函数。我修改了接受输入的方式，但逻辑保持不变。

void solve() {
    string str; cin >> str; // chilhood string
    
    int n; cin >> n;
    
    vector<string> v(n);   // other strings
    for(string& s: v) cin >> s;
    
    // table
    vector<vector<bool>> dp(str.size(), vector<bool>(n, false));
    for(int i=0; i<str.size(); i++) {
        for(int j=0; j<n; j++) {
            dp[i][j] = (v[j].find(str[i]) != string::npos) ? true: false;
        }
    }
    
    unordered_set<int> row, col;
    for(int i=0; i<str.size(); i++) {
        for(int j=0; j<n; j++) {
            if(dp[i][j] == true) {
                row.insert(i);
                col.insert(j);
            }
        }
    }

    cout << ((row.size() == str.size() && col.size() >= str.size()) ? "true": "false") << '\n';
}