如何检查字母是否在字符串中？

Question

这是一个很难问的问题，但我会尝试。 我有 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**

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

Answer 1

你的方法只有几行...

   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;
    }

Answer 2

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

C-Sharpish 伪代码：（可能不会按编写的方式编译）

/** 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;
}

Answer 3

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