How check if letters are in string?

Question

It quite hard question to ask but I will try. I have my 4 letters m u g o . I have also free string word(s).
Let'say: og ogg muogss. I am looking for any wise method to check if I can construct word(s) using only my letters. Please take notice that we used once g we won't be able to use it again.

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**

So my tactic is take my letters to char array and remove one by one and check how many left to build the word(s). But is it possible to use somehow in few lines, i do not know - regex ?

"Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems." - Jamie Zawinski — neeKo, Nov 08 '11 at 22:18
There are only 10 types of people in the world: Those who understand binary, and those who don't - little digression :) — deadfish, Nov 08 '11 at 22:27

Keith Nicholas · Accepted Answer · 2011-11-08T22:44:37.057

8

your method is only a few lines...

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

edited Nov 08 '11 at 22:44

answered Nov 08 '11 at 22:31

Keith Nicholas

43,549
15
93
156

this LINQ is awesome :) Thanks Sir! – deadfish Nov 09 '11 at 22:51

Keith Irwin · Answer 2 · 2011-11-08T22:36:45.677

Here's a simple approach: For your source word, create an array of size 26 and use it to count the how many times each letter appears. Do the same for each word in your dictionary. Then compare the two. If every letter occurs less than or equal to as many times in the dictionary word as the source word, then it can be used to make that word. If not, then it cannot.

C-Sharpish Pseudocode: (probably doesn't compile as written)

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

@L.B You can modify it to work for other phonetic alphabets by changing the size of the alphabet and the charToLetter function. Because I can't quickly recognize which letters are which, I'm not sure if that's simplified Chinese, traditional Chinese, Japanese kanji, hiragana, or katakana. But if it's one of the large ones, you'd probably also want to switch to a hash table since otherwise you'd have a very, very sparse array to check. That would complicate the code a little, but the same fundamental method would work. — Keith Irwin, Nov 08 '11 at 22:45
@KeithIrwin You take it too seriously. It was just a fun. But a hashtable/array for UTF32 would be quite large :). — L.B, Nov 08 '11 at 22:49

score 0 · Answer 3 · answered Nov 08 '11 at 22:17

If your definition of words is any arbitrary permutation of the available charactters then why do you need a regex? Just make sure you use each characters once. Regex doesn't know what a "correct word" is, and it's better to avoid using invalid characters by your algorithms than using them AND using a regex to make sure you didn't use them.

How check if letters are in string?

3 Answers3