Check if string is subset of a bunch of characters? (RegEx)?

Question

I have a little problem, I have 8 characters, for example "a b c d a e f g", and a list of words, for example: mom, dad, bad, fag, abac

How can I check if I can or cannot compose these words with the letters I have? In my example, I can compose bad, abac and fag, but I cannot compose dad (I have not two D) and mom (I have not M or O).

I'm pretty sure it can be done using a RegEx but would be helpful even using some functions in Perl.. Thanks in advance guys! :)

Answer 1

This is done most simply by forming a regular expression from the word that is to be tested.

This sorts the list of available characters and forms a string by concatenating them. Then each candidate word is split into characters, sorted, and rejoined with the regex term .* as separator. So, for instance, abac will be converted to a.*a.*b.*c.

Then the validity of the word is determined by testing the string of available characters against the derived regex.

use strict;
use warnings;

my @chars = qw/ a b c d a e f g /;
my $chars = join '', sort @chars;

for my $word (qw/ mom dad bad fag abac /) {
  my $re = join '.*', sort $word =~ /./g;
  print "$word is ", $chars =~ /$re/ ? 'valid' : 'NOT valid', "\n";
}

output

mom is NOT valid
dad is NOT valid
bad is valid
fag is valid
abac is valid

Answer 2

This is to demonstrate the possibility rather than endorsing the regex method. Please consider other saner solution.

First step, you need to count the number of characters available.

Then construct your regex as such (this is not Perl code!):

Start with start of input anchor, this matches the start of the string (a single word from the list):

^

Append as many of these as the number of unique characters:

(?!(?:[^<char>]*+<char>){<count + 1>})

Example: (?!(?:[^a]*+a){3}) if the number of a is 2.

I used an advanced regex construct here called zero-width negative look-ahead (?!pattern). It will not consume text, and it will try its best to check that nothing ahead in the string matches the pattern specified (?:[^a]*+a){3}. Basically, the idea is that I check that I cannot find 3 'a' ahead in the string. If I really can't find 3 instances of 'a', it means that the string can only contain 2 or less 'a'.

Note that I use *+, which is 0 or more quantifier, possessively. This is to avoid unnecessary backtracking.

Put the characters that can appear within []:

[<unique_chars_in_list>]+

Example: For a b c d a e f g, this will become [abcdefg]+. This part will actually consume the string, and make sure the string only contains characters in the list.

End with end of input anchor, which matches the end of the string:

$

So for your example, the regex will be:

^(?!(?:[^a]*+a){3})(?!(?:[^b]*+b){2})(?!(?:[^c]*+c){2})(?!(?:[^d]*+d){2})(?!(?:[^e]*+e){2})(?!(?:[^f]*+f){2})(?!(?:[^g]*+g){2})[abcdefg]+$

You must also specify i flag for case-insensitive matching.

Note that this only consider the case of English alphabet (a-z) in the list of words to match. Space and hyphen are not (yet) considered here.

Answer 3

How about sorting both strings into alphabetical order then for the string you want to check insert .* between each letter like so:

'aabcdefg' =~ m/a.*b.*d.*/
True
'aabcdefg' =~ m/m.*m.*u.*/
False
'aabcdefg' =~ m/a.*d.*d.*/
False

Answer 4

Some pseudocode:

• Sort the available characters into alphabetical order

• for each word:

  • Sort the characters of the word into alphabetical order
    • For each character of the word search forwards through the available characters to find a matching character. Note the this search will never go back to the start of the available chars, matched chars are consumed.

Or even better, use frequency counts of characters. For your available characters, construct a map from character to occurence count of that character. Do the same for each candidate word and compare against the available map, if the word map contains a mapping for a character where the available map does not, or the mapped value is larger in the word map than the available map, then the word cannot be constructed using the available characters.

Answer 5

Here's a really simple script that would be rather easy to generalize:

#!/usr/bin/env perl

use strict;
use warnings;

sub check_word {
  my $word = shift;
  my %chars;
  $chars{$_}++ for @_;
  $chars{$_}-- or return for split //, $word;
  return 1;
}

print check_word( 'cab', qw/a b c/ ) ? "Good" : "Bad";

And of course the performance of this function could be greatly enhanced if the letters list is going to be the same every time. Actually for eight characters, copying the hash vs building a new one each time is probably the same speed.

Answer 6

pseudocode:

bool possible=true
string[] chars= { "a", "b", "c"}   
foreach word in words
{
     foreach char in word.chars
     {
          possible=possible && chars.contains(char)
     }
}