1

我有一个小问题，我有 8 个字符，例如“abcdaef g”，还有一个单词列表，例如：mom、dad、bad、fag、abac

我如何检查我是否可以用我拥有的字母组成这些单词？在我的示例中，我可以组成 bad、abac 和 fag，但我不能组成 dad（我没有两个 D）和 mom（我没有 M 或 O）。

我很确定它可以使用 RegEx 来完成，但即使在 Perl 中使用某些函数也会有所帮助。在此先感谢各位！:)

4

6 回答 6

6

最简单的方法是从要测试的单词中形成一个正则表达式。

这会对可用字符列表进行排序，并通过连接它们形成一个字符串。然后每个候选词被分割成字符，排序，并用正则表达式.*作为分隔符重新连接。因此，例如，abac将转换为a.*a.*b.*c.

然后通过针对派生的正则表达式测试可用字符的字符串来确定单词的有效性。

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

输出

mom is NOT valid
dad is NOT valid
bad is valid
fag is valid
abac is valid
于 2013-01-17T16:59:16.680 回答
3

这是为了证明这种可能性，而不是支持正则表达式方法。请考虑其他更明智的解决方案。

第一步，您需要计算可用字符数。

然后像这样构造你的正则表达式（这不是 Perl 代码！）：

从输入锚的开头开始，这匹配字符串的开头（列表中的单个单词）：

^

附加与唯一字符数一样多的这些：

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

示例：(?!(?:[^a]*+a){3})如果数量a为 2。

我在这里使用了一种高级正则表达式构造，称为零宽度负前瞻(?!pattern)。它不会使用文本，并且会尽力检查字符串中前面的内容是否与指定的模式匹配(?:[^a]*+a){3}。基本上，我的想法是检查我在字符串中是否找不到 3 'a'。如果我真的找不到 3 个 'a' 的实例，则意味着该字符串只能包含 2 个或更少的 'a'。

请注意，我使用*+，这是 0 或更多的量词，所有格。这是为了避免不必要的回溯。

将可以出现的字符放入[]：

[<unique_chars_in_list>]+

示例：对于a b c d a e f g，这将变为[abcdefg]+。这部分实际上会消耗字符串，并确保字符串只包含列表中的字符。

以输入锚的结尾结尾，它匹配字符串的结尾：

$

因此，对于您的示例，正​​则表达式将是：

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

i您还必须为不区分大小写的匹配指定标志。

请注意，这仅考虑要匹配的单词列表中英文字母 (az) 的情况。此处（尚未）考虑空格和连字符。

于 2013-01-17T16:22:19.170 回答
1

如何将两个字符串按字母顺序排序，然后为要检查的字符串在每个字母之间插入 .*，如下所示：

'aabcdefg' =~ m/a.*b.*d.*/
True
'aabcdefg' =~ m/m.*m.*u.*/
False
'aabcdefg' =~ m/a.*d.*d.*/
False
于 2013-01-17T16:54:19.780 回答
0

一些伪代码：

  • 将可用字符按字母顺序排序

  • 对于每个单词：

    • 将单词的字符按字母顺序排序
      • 对于单词的每个字符，向前搜索可用字符以找到匹配的字符。请注意，此搜索永远不会回到可用字符的开头，匹配的字符会被消耗。

甚至更好的是，使用字符的频率计数。对于您可用的字符，构建一个从字符到该字符出现计数的映射。对每个候选词执行相同操作并与可用映射进行比较，如果词映射包含可用映射不存在的字符的映射，或者词映射中的映射值大于可用映射，则该词不能使用可用的字符构造。

于 2013-01-17T16:25:08.530 回答
0

这是一个非常简单的脚本，很容易概括：

#!/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";

当然，如果字母列表每次都相同，则此功能的性能会大大提高。实际上对于八个字符，每次复制哈希与构建一个新的哈希可能是相同的速度。

于 2013-01-17T22:52:09.887 回答
-2

伪代码：

bool possible=true
string[] chars= { "a", "b", "c"}   
foreach word in words
{
     foreach char in word.chars
     {
          possible=possible && chars.contains(char)
     }
}
于 2013-01-17T16:12:28.380 回答