2

这是一个很难问的问题，但我会尝试。我有我的 4 个字母m u g o。我也有免费的字符串字（s）。
比方说：og ogg muogss。我正在寻找任何明智的方法来检查我是否可以仅使用我的字母来构造单词（ s ）。请注意，我们使用过一次，g我们将无法再次使用它。

og - possible because we need only **g** and **o**
ogg - not possible we took **o** and **g**, need the second **g**
muogss - not possible we took all, need also additional **s**

所以我的策略是将我的字母带到 char 数组中，然后一个一个地删除，然后检查剩下多少个来构建单词（s）。但是是否可以在几行中以某种方式使用，我不知道 - 正则表达式？

4

3 回答 3

8

你的方法只有几行......

   public static bool CanBeMadeFrom(string word, string letters)
    {
        foreach (var i in word.Select(c => letters.IndexOf(c, 0)))
        {
            if (i == -1) return false;
            letters = letters.Remove(i, 1);
        }
        return true;
    }
于 2011-11-08T22:31:43.493 回答
3

这是一个简单的方法：对于您的源词，创建一个大小为 26 的数组，并使用它来计算每个字母出现的次数。对字典中的每个单词执行相同的操作。然后比较两者。如果每个字母在字典单词中出现的次数少于或等于源单词的次数，则可以使用它来制作该单词。如果不是，那么它不能。

C-Sharpish Pseudocode：（可能无法按书面方式编译）

/** Converts characters to a 0 to 25 code representing alphabet position.
    This is specific to the English language and would need to be modified if used
    for other languages. */
int charToLetter(char c) {
    return Char.ToUpper(c)-'A';
}

/** Given a source word and an array of other words to check, returns all 
    words from the array which can be made from the letters of the source word. */
ArrayList<string> checkSubWords(string source, string[] dictionary) {

    ArrayList<string> output = new ArrayList<string>();

    // Stores how many of each letter are in the source word.
    int[] sourcecount = new int[26];  // Should initialize to 0, automatically
    foreach (char c in source) {
        sourcecount[c]++;
    }

    foreach (string s in dictionary) {

        // Stores how many of each letter are in the dictionary word.
        int[] dictcount = new int[26]; // Should initialize to 0, automatically
        foreach (char c in s) {
            dictcount[c]++;
        }

        // Then we check that there exist no letters which appear more in the 
        // dictionary word than the source word.
        boolean isSubword = true;
        for (int i=0;i<26;i++) {
            if (dictcount[i] > sourcecount[i]) {
                isSubword = false;
            }
        }

        // If they're all less than or equal to, then we add it to the output.
        if (isSubWord) {
            output.add(s);
        }
    }
    return output;
}
于 2011-11-08T22:19:35.343 回答
0

如果您对单词的定义是可用字符的任意排列，那么您为什么需要正则表达式？只需确保您使用每个字符一次。正则表达式不知道什么是“正确的单词”，最好避免在算法中使用无效字符，而不是使用它们并使用正则表达式来确保您没有使用它们。

于 2011-11-08T22:17:06.860 回答